Problem Description

A tree is a connected graph with $n$ nodes and $n-1$ edges.

You are given a weighted tree with $n$ nodes. The $i$-th node has a weight of $wn_i$ and a cost of $c_i$. The $i$-th edge connecting node $u_i$ and $v_i$ has a weight of $we_i$. The edge is called beautiful if and only if it meets $\min(wn_{u_i}, wn_{v_i}) \le we_i \le \max(wn_{u_i}, wn_{v_i})$.

You can do the following operation several times.

• Choose a node $u$, then change its weight $wn_u$ into $wn^{\prime}_{u}$. The total cost adds $c_u \left| wn_u - wn^{\prime}_{u} \right|$.

What is the minimum total cost to make all edges beautiful?

Input

The first line contains an integer $T$, denoting the number of test cases.

For each test case, the input format is as follows:

| $n$ | | | | |
|-----------|-----------|------------|----------|--------|
| $c_1$ | $c_2$ | $c_3$ | $\ldots$ | $c_n$ |
| $wn_1$ | $wn_2$ | $wn_3$ | $\ldots$ | $wn_n$ |
| $u_1$ | $v_1$ | $we_1$ | | |
| $u_2$ | $v_2$ | $we_2$ | | |
| $\vdots$ | $\vdots$ | $\vdots$ | | |
| $u_{n-1}$ | $v_{n-1}$ | $we_{n-1}$ | | |

It is guaranteed that:

• $1\le T \le 10^3$
• $1\le n \le 10^5$, $\sum n\le 10^6$
• $1\le c_i, wn_i, we_i \le 10^6$

Output

For each test case, output an integer in a single line, denoting the minimum total cost.

2
3
2 1 2
9 9 10
1 2 10
1 3 11
3
1 1 2
9 9 10
1 2 10
1 3 11

3
2