Chef and Minimum Cost of His Tree

 You are a given a tree of 

N$N$ vertices. The i$i$-th vertex has two things assigned to it — a value Ai$A_i$ and a range [Li,Ri]$[L_i,R_i]$. It is guaranteed that Li≤Ai≤Ri$L_i\le A_i\le R_i$.

You perform the following operation exactly once:

• Pick a (possibly empty) subset S$S$ of vertices of the tree. S$S$ must satisfy the additional condition that no two vertices in S$S$ are directly connected by an edge, i.e, it is an independent set.
• Then, for each x∈S$x\in S$, you can set Ax$A_x$ to any value in the range [Lx,Rx]$[L_x,R_x]$ (endpoints included).

Your task is to minimize the value of ∑|Au−Av|$\sum |A_u-A_v|$ over all unordered pairs (u,v)$(u,v)$ such that u$u$ and v$v$ are connected by an edge.

Input Format

• The first line of input will contain a single integer T$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$N$, the number of vertices.
  • The next N$N$ lines describe the values of the vertices. The i$i$-th of these N$N$ lines contains three space-separated integers Li$L_i$, Ai$A_i$, and Ri$R_i$ respectively
  • The next N−1$N-1$ lines describe the edges. The i$i$-th of these N−1$N-1$ lines contains two space-separated integers ui$u_i$ and vi$v_i$, denoting an edge between ui$u_i$ and vi$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≤104$1\le T\le {10}^4$
• 3≤N≤105$3\le N\le {10}^5$
• 1≤ui,vi≤N$1\le u_i,v_i\le N$
• ui≠vi$u_i\ne v_i$ for each 1≤i≤N−1$1\le i\le N-1$
• 1≤Li≤Ai≤Ri≤109$1\le L_i\le A_i\le R_i\le {10}^9$
• The sum of N$N$ over all test cases won't exceed 2⋅105$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

Test case 1$1$: Set the value of A2$A_2$ to 2$2$. The answer is |A1−A2|+|A1−A3|=|1−2|+|1−3|=3$|A_1-A_2|+|A_1-A_3|=|1-2|+|1-3|=3$.

Test case 2$2$: Set the value of A2$A_2$ to 2$2$. The answer is .