Description

In NTHU, there are numerous Oloo stations interconnected by roads forming a tree structure. Each road has its passage time.

To ensure easy access for everyone to borrow Oloo, the operating company need to redistribute Oloo among stations during night so that each station has an equal number of Oloos.

You're given a tree consisting of $N$ nodes and $N-1$ edges, representing the map of NTHU campus. Each node is an Oloo station number from $0$ to $N - 1$, and the number of Oloo in Oloo station $i$ is denoted as $a_i$. The edges are represented by (u, v, w), where edge (u, v) connects node $u$ and node $v$, and the time required to traverse this edge is denoted by $w$.

The total cost of redistributing Oloo is calculated as the sum of distances each Oloo is moved, considering the passage time of each road. The objective is to minimize this cost. Write a program to help calculate the minimum cost.

Input

The first line contains an integer $T$, which is the number of testcases. For each testcase:

• The first line contains an integer $N$, which is the number of oloo station.
• The second line contains $N$ integers $a_1, a_2, \dots, a_N$, which are the number of Oloo in each station.
• The following $N-1$ lines of each testcase contain three integers $u_i, v_i, w_i$, which means there is a road connects $u_i$ and $v_i$, and the cost of road is $w_i$.

$N$
$a_1 \quad a_2 \quad \dots \quad a_N$
$u_1 \quad v_1 \quad w_1$
$u_2 \quad v_2 \quad w_2$
$\vdots$
$u_{N-1} \quad v_{N-1} \quad w_{N-1}$

Constraints

• $1 \le T \le 5$
• $0 \le u_i, v_i < N$
• $1 \le w_i \le 1000$
• For testcase 1~3:
  • $1 \le N \le 500$
  • $0 \le a_i \le 1000$
• For testcase 4~6:
  • $1 \le N \le 2 * 10^5$
  • $0 \le a_i \le 1000$
• For testcase 7~9:
  • $1 \le N \le 2 * 10^5$
  • $0 \le a_i \le 10^7$

Output

For each testcase, output its minimum cost. If it's impossible, print -1 as the answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss