You are a given a tree of N vertices. The i-th vertex has two things assigned to it — a value A_{i} and a range [L_{i}, R_{i}]. It is guaranteed that L_{i} ≤ A_{i} ≤ R_{i}.

You perform the following operation exactly once:
Pick a (possibly empty) subset S of vertices of the tree. S must satisfy the additional condition that no two vertices in S are directly connected by an edge, i.e, it is an [independent set].
Then, for each $x \in$ S, you can set A_{x} to any value in the range [L_{x}, R_{x}] (endpoints included).

Your task is to minimize the value of $\sum |A_{u} - A_{v}|$ over all unordered pairs (u, v) such that u and v are connected by an edge.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains a single integer N, the number of vertices.
• The next N lines describe the values of the vertices. The i-th of these N lines contains three space-separated integers L_{i}, A_{i}, and R_{i} respectively
• The next N-1 lines describe the edges. The i-th of these N-1 lines contains two space-separated integers u_{i} and v_{i}, denoting an edge between u_{i} and v_{i}.

------ Output Format ------

For each test case, output on a new line the minimum possible value as described in the statement.

------ Constraints ------

$1 ≤ T ≤ 10^{4}$
$3 ≤ N ≤ 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
$u_{i} \neq v_{i}$ for each $1 ≤ i ≤ N-1$
$1 ≤ L_{i} ≤ A_{i} ≤ R_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
2
3
1 1 1
2 3 3
3 3 3
1 2
1 3
4
3 3 4
1 3 5
2 2 2
2 2 2
1 2
2 3
2 4

----- Sample Output 1 ------
3
1
----- explanation 1 ------
Test case $1$: Set the value of $A_{2}$ to $2$. The answer is $|A_{1} - A_{2}| + |A_{1} - A_{3}| = |1 - 2| + |1 - 3| = 3$.

Test case $2$: Set the value of $A_{2}$ to $2$. The answer is $|A_{1} - A_{2}| + |A_{2} - A_{3}| + |A_{2} - A_{4}| = |3 - 2| + |2 - 2| + |2 - 2| = 1$.

见题面

见题面