Tangling Tree

 You are given an undirected tree of 

N$N$ nodes. A positive weight Wi$W_i$ is assigned to the node i$i$ for all 1≤i≤N$1\le i\le N$.

For all 1≤j≤N−1$1\le j\le N-1$, the j$j$-th edge connects the nodes uj$u_j$ and vj$v_j$, and has a restriction value of Rj$R_j$.

An array A1,A2,⋯,AN$A_1,A_2,\cdots ,A_N$ consisting of N$N$ non-negative integers is called valid if:

• For all 1≤j≤N−1$1\le j\le N-1$, the condition Auj+Avj≤Rj$A_{u_j}+A_{v_j}\le R_j$ holds.

The profit of a valid array A$A$ is defined as

profit(A)=∑i=1NAi⋅Wi$$profit(A)=\sum _{i=1}^N{A}_i\cdot W_i$$

Find the maximum possible value of profit(A)$profit(A)$ for some valid array A$A$.

Input Format

• The first line of input contains a single integer T$T$ - the number of test cases. The description of T$T$ test cases follow.
• The first line of each test case contains a single integer N$N$ - the number of nodes in the tree.
• The second line of each test case contains N$N$ integers W1,W2,⋯,WN$W_1,W_2,\cdots ,W_N$ denoting the weights assigned to every node.
• The next N−1$N-1$ lines contain three space-separated integers each, with the j$j$-th line containing uj$u_j$, vj$v_j$, and Rj$R_j$.

Output Format

For each test case, output the maximum possible value of profit(A)$profit(A)$.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 3≤N≤105$3\le N\le {10}^5$
• 1≤Wi≤109$1\le W_i\le {10}^9$
• 1≤uj,vj≤N$1\le u_j,v_j\le N$ and uj≠vj$u_j\ne v_j$
• 1≤Rj≤109$1\le R_j\le {10}^9$
• It is guaranteed that N⋅maxNi=1Wi⋅maxN−1j=1Rj≤1018.$N\cdot {\text{max}}_{i=1}^N{W}_i\cdot {\text{max}}_{j=1}^{N-1}{R}_j\le {10}^{18}.$
• It is guaranteed that the input forms a valid tree for all test cases.
• The sum of N$N$ over all test cases do not exceed 105${10}^5$

Sample Input 1 

3
3
6 9 4
1 2 2
2 3 1
6
1 2 2 6 100 100
1 2 9
2 3 17
2 4 3
3 5 1
3 6 4
3
120734269 1000000000 1
1 2 300000000
2 3 300000000

Sample Output 1 

16
527
300000000000000000

Explanation

Test case-1: All valid arrays A$A$ are:

• A=[0,0,0]$A=[0,0,0]$; profit(A)=0⋅6+0⋅9+0⋅4=0$profit(A)=0\cdot 6+0\cdot 9+0\cdot 4=0$
• A=[0,0,1]$A=[0,0,1]$; profit(A)=0⋅6+0⋅9+1⋅4=4$profit(A)=0\cdot 6+0\cdot 9+1\cdot 4=4$
• A=[0,1,0]$A=[0,1,0]$; profit(A)=0⋅6+1⋅9+0⋅4=9$profit(A)=0\cdot 6+1\cdot 9+0\cdot 4=9$
• A=[1,0,1]$A=[1,0,1]$; profit(A)=1⋅6+0⋅9+1⋅4=10$profit(A)=1\cdot 6+0\cdot 9+1\cdot 4=10$
• A=[1,1,0]$A=[1,1,0]$; profit(A)=1⋅6+1⋅9+0⋅4=15$profit(A)=1\cdot 6+1\cdot 9+0\cdot 4=15$
• A=[2,0,1]$A=[2,0,1]$; profit(A)=2⋅6+0⋅9+1⋅4=16$profit(A)=2\cdot 6+0\cdot 9+1\cdot 4=16$

The maximum profit among all valid arrays A$A$ is 16$16$, which is the answer.

Test case-2: The optimal A$A$ is [9,0,0,3,1,4]$[9,0,0,3,1,4]$.

Test case-3: The optimal A$A$ is [0,300000000,0]$[0,300000000,0]$.