Tree Master Problem Code: TRMT Add problem to Todo list Submit Given is a tree with N weighted vertices and N1 weighted edges. The i-th vertex has a weight of Ai. The i-th edge has a weight of Wi and connects vertices ui and vi.

Let dist(x,y) be the sum of weights of the edges in the unique simple path connecting vertices x and y.

Let V(x,y) be the set of vertices appearing in the unique simple path connecting vertices x and y (including x and y).

You are asked Q queries. In the i-th query, you are given two integers xi and yi and you need to compute:

kV(xi,yi)(dist(xi,k)dist(k,yi))Ak Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows. The first line contains two integers N and Q. The second line contains N integers A1,A2,,AN. Each of the next N1 lines contains three integers ui, vi and Wi. Each of the next Q lines contains two integers xi and yi. Output Format For each query, print the answer to it on a new line.

Constraints 1T103 2N2105 1Q2105 1Ai,Wi104 1ui,vi,xi,yiN xiyi uivi The sum of N across all test cases does not exceed 2105. The sum of Q across all test cases does not exceed 2105. Subtasks Subtask #1 (20 points): ui=i,vi=i+1 Subtask #2 (80 points): Original constraints Sample Input 1 2 5 2 5 3 3 1 2 1 2 2 2 3 1 2 4 1 1 5 2 4 5 5 4 10 5 3 6 9 2 3 8 3 7 9 7 1 2 4 1 3 6 1 4 8 4 5 9 1 6 2 5 7 3 3 8 7 3 9 2 7 10 9 9 2 2 1 8 5 3 2 3 10 Sample Output 1 1 -1 -96 -12 -252 -24 -69 Explanation Test Case 1:

For the first query, V(4,5)={4,2,1,5}. The answer is 1(05)+3(14)+5(32)+2(50)=1 For the second query, V(5,4)={5,1,2,4}. The answer is 2(05)+5(23)+3(41)+1(50)=1