310931: CF1910J. Two Colors

J. Two Colorstime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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.

ExamplesInput

4
1 1 0 0
3 4 50
3 2 100
2 1 100

Output

350

Input

6
0 1 0 1 0 1
1 2 1
1 4 1
1 6 1
6 5 100
6 3 100

Output

203

Input

3
1 1 1
1 2 100
2 3 100

Output

Infinity

Note

In the first example, you can assign $v_1 = 120, v_2 = 20, v_3 = 80, v_4 = 130$.

题目大意：
你有一棵由n个顶点组成的树。树的一些顶点是红色的，所有其他顶点是蓝色的。每条边都有一个正权重。定义d(x, y)为顶点x和y之间的距离，即属于x和y之间简单路径的边的权重之和。对于每个顶点，你必须选择一个整数v_i。这些整数应满足以下约束：对于每个蓝色顶点b和每个红色顶点r，d(b, r) ≥ v_b + v_r。你需要最大化Σv_i的值。注意，v_i的值不一定为正。

输入输出数据格式：
输入：
- 第一行包含一个整数n（2≤n≤3×10^5）。
- 第二行包含n个整数c_1, c_2, …, c_n（0≤c_i≤1）。如果第i个顶点是红色的，c_i = 1，否则c_i = 0。
- 接下来的n-1行。每行包含三个整数x_i, y_i和w_i（1≤x_i, y_i≤n；1≤w_i≤10^6；x_i ≠ y_i），表示顶点x_i和y_i之间的一条边，该边的权重为w_i。这些边构成一棵树。

输出：
- 如果Σv_i的值尽可能大，则打印Infinity。否则，打印一个整数——你可以得到的Σv_i的最大可能值。题目大意： 你有一棵由n个顶点组成的树。树的一些顶点是红色的，所有其他顶点是蓝色的。每条边都有一个正权重。定义d(x, y)为顶点x和y之间的距离，即属于x和y之间简单路径的边的权重之和。对于每个顶点，你必须选择一个整数v_i。这些整数应满足以下约束：对于每个蓝色顶点b和每个红色顶点r，d(b, r) ≥ v_b + v_r。你需要最大化Σv_i的值。注意，v_i的值不一定为正。 输入输出数据格式： 输入： - 第一行包含一个整数n（2≤n≤3×10^5）。 - 第二行包含n个整数c_1, c_2, …, c_n（0≤c_i≤1）。如果第i个顶点是红色的，c_i = 1，否则c_i = 0。 - 接下来的n-1行。每行包含三个整数x_i, y_i和w_i（1≤x_i, y_i≤n；1≤w_i≤10^6；x_i ≠ y_i），表示顶点x_i和y_i之间的一条边，该边的权重为w_i。这些边构成一棵树。 输出： - 如果Σv_i的值尽可能大，则打印Infinity。否则，打印一个整数——你可以得到的Σv_i的最大可能值。