J. Moufless Tree Surgery
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices. Vertex $$$i$$$ initially contains $$$a_i$$$ integer units of value.

For an edge $$$(u, v)$$$ with cost $$$w$$$, moving one unit of value from $$$u$$$ to $$$v$$$ costs $$$w$$$, and moving one unit from $$$v$$$ to $$$u$$$ also costs $$$w$$$. You may perform any number of such transfers. The final values of all vertices must be integers, and the total amount of value is preserved.

Let the final values be $$$b_1, b_2, \ldots, b_n$$$. Your primary goal is to minimize the difference between the maximum and minimum final values. Formally, you must minimize

$$$$$$\max(b_1, b_2, \dots, b_n) - \min(b_1, b_2, \dots, b_n)$$$$$$

Among all ways to obtain this minimum possible difference, find the minimum possible total transfer cost.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case begins with a line containing one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — the initial values of the vertices.

Each of the next $$$n-1$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$1 \le w \le 10^4$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$ with cost $$$w$$$ per moved unit.

The given edges form a tree. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print one integer — the minimum total transfer cost among all final configurations with minimum possible value difference.

Example
Input
4
2
1 3
1 2 5
3
1 1 5
1 2 4
2 3 7
4
10 1 1 1
1 2 1
1 3 10
1 4 100
5
6 6 6 6 6
1 2 3
2 3 4
3 4 5
4 5 6
Output
5
18
222
0
Note

In the first test case, the total value is $$$4$$$, so both vertices must end with value $$$2$$$. One unit is moved through the only edge, for a cost of $$$5$$$.

In the second test case, the total value is $$$7$$$. The minimum possible difference is $$$1$$$, and the final values must be two vertices with value $$$2$$$ and one vertex with value $$$3$$$. It is optimal to leave vertex $$$3$$$ with value $$$3$$$, move one unit from vertex $$$3$$$ to vertex $$$2$$$, and then move one unit from vertex $$$2$$$ to vertex $$$1$$$, for a total cost of $$$18$$$.

In the third test case, the only optimal choice is to make the center vertex have value $$$4$$$ and the leaves have value $$$3$$$.

In the fourth test case, all values are already equal, so the answer is $$$0$$$.