Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a tree with $N$ vertices (numbered $1$ through $N$). Its edges are numbered $1$ through $N-1$. For each valid $i$, there is an integer $a_{i}$ written on the $i$-th vertex. Also, for each valid $i$, there is an integer $b_{i}$ written on the $i$-th edge.

You want the following condition to be satisfied: for each vertex $v$ and each edge $e$ adjacent to $v$, $a_{v} ≥ b_{e}$. In order to achieve that, you may perform an arbitrary number of steps (including zero). In one step, you may perform one the following operations:
1. Select two different vertices $u$ and $v$. Swap $a_{u}$ and $a_{v}$.
2. Select two different edges $e$ and $f$. Swap $b_{e}$ and $b_{f}$.
3. Select a vertex $v$ and an integer $x$. Change $a_{v}$ to $x$ and pay one coin.

Calculate the minimum number of coins you need in order to satisfy the required condition.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N-1$ lines follow. For each $i$ ($1 ≤ i ≤ N-1$), the $i$-th of these lines contains three space-separated integers $u_{i}$, $v_{i}$ and $b_{i}$ denoting that the $i$-th edge connects vertices $u_{i}$ and $v_{i}$ and the initial value written on it is $b_{i}$.
The last line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.

------ Output ------
For each test case, print a single line containing one integer ― the minimum necessary number of coins.

------ Constraints ------
$1 ≤ T ≤ 10$
$2 ≤ N ≤ 100,000$
$1 ≤ u_{i}, v_{i} ≤ N$ for each valid $i$
$1 ≤ b_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ a_{i} ≤ 10^{9}$ for each valid $i$
the graph on the input is a tree

------ Subtasks ------
Subtask #1 (10 points): $N ≤ 7$

Subtask #2 (10 points): $N ≤ 10$

Subtask #3 (30 points): $N ≤ 200$

Subtask #4 (50 points): original constraints

----- Sample Input 1 ------
1

3

1 2 4

2 3 7

1 5 10
----- Sample Output 1 ------
1
----- explanation 1 ------
Example case 1: There is no way to satisfy the required condition without paying any coins. When we have one coin, we can perform the following operations:
- Swap the integers written on vertices $1$ and $2$.
- Pay one coin and change the integer written on vertex $2$ to $7$.

见题面

见题面