You are given a tree consisting of $n$ vertices. Some vertices of the tree are red, all other vertices are blue.

Each edge of the tree has a positive weight. Let's define $d(x, y)$ as the distance between the vertices $x$ and $y$, i. e. the sum of weights of edges belonging to the simple path between $x$ and $y$.

For each vertex, you have to choose an integer $v_i$. These integers should meet the following constraint: for every blue vertex $b$ and every red vertex $r$, $d(b, r) \ge v_b + v_r$.

You have to maximize the value of $\sum \limits_{i=1}^{n} v_i$.

Note that the values of $v_i$ are not necessarily positive.

The first line contains one integer $n$ ($2 \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($0 \le c_i \le 1$). If the $i$-th vertex is red, $c_i = 1$, otherwise $c_i = 0$.

Then $n-1$ lines follow. Each line contains three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i, y_i \le n$; $1 \le w_i \le 10^6$; $x_i \ne y_i$) denoting an edge between the vertices $x_i$ and $y_i$ which has weight $w_i$. These edges form a tree.

If the value of $\sum \limits_{i=1}^{n} v_i$ can be as big as possible, print Infinity. Otherwise, print one integer — the maximum possible value of $\sum \limits_{i=1}^{n} v_i$ you can get.