J. Два цвета
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин. Некоторые вершины дерева — красные, все остальные — синие.

У каждого ребра дерева есть вес — положительное целое число. Обозначим за $$$d(x, y)$$$ расстояние между вершинами $$$x$$$ и $$$y$$$, т. е. сумму весов ребер, принадлежащих простому пути от $$$x$$$ до $$$y$$$.

Для каждой вершины вы должны выбрать целое число $$$v_i$$$. Эти числа должны удовлетворять следующему ограничению: для каждой синей вершины $$$b$$$ и каждой красной вершины $$$r$$$ должно выполняться $$$d(b, r) \ge v_b + v_r$$$.

Вам нужно максимизировать величину $$$\sum \limits_{i=1}^{n} v_i$$$.

Обратите внимание, что значения $$$v_i$$$ не обязательно должны быть положительными.

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$). Если $$$i$$$-я вершина — красная, $$$c_i = 1$$$, иначе $$$c_i = 0$$$.

Затем следуют $$$n-1$$$ строк. В каждой из них заданы три целых числа $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$1 \le w_i \le 10^6$$$; $$$x_i \ne y_i$$$), обозначающих ребро между вершинами $$$x_i$$$ и $$$y_i$$$ с весом $$$w_i$$$. Эти ребра образуют дерево.

Выходные данные

Если значение $$$\sum \limits_{i=1}^{n} v_i$$$ может быть сколько угодно большим, выведите Infinity. Иначе, выведите одно целое число — максимальное значение $$$\sum \limits_{i=1}^{n} v_i$$$, которое вы можете получить.

Примеры
Входные данные
4
1 1 0 0
3 4 50
3 2 100
2 1 100
Выходные данные
350
Входные данные
6
0 1 0 1 0 1
1 2 1
1 4 1
1 6 1
6 5 100
6 3 100
Выходные данные
203
Входные данные
3
1 1 1
1 2 100
2 3 100
Выходные данные
Infinity
Примечание

В первом примере можно использовать $$$v_1 = 120, v_2 = 20, v_3 = 80, v_4 = 130$$$.