Bookshop
Problem Description
DreamGrid will go to the bookshop tomorrow. There are $n$ books in the bookshop in total, labeled by $1,2,\dots,n$, connected by $n-1$ bidirectional roads like a tree. Because DreamGrid is very rich, he will buy the books according to the strategy below:
- Select two books $x$ and $y$.
- Walk from $x$ to $y$ along the shortest path on the tree, and check each book one by one, including the $x$-th book and the $y$-th book.
- For each book being checked now, if DreamGrid has enough money (not less than the book price), he'll buy the book and his money will be reduced by the price of the book. In case that his money is less than the price of the book being checked now, he will skip that book.
Input
The first line contains a single integer $T$ ($1 \leq T \leq 500$), the number of test cases. For each test case:
The first line of the input contains two integers $n$ and $q$ ($1 \leq n,q \leq 100\,000$), denoting the number of books in the bookshop and the number of queries.
The second line contains $n$ integers $p_1,p_2,\dots,p_n$ ($1\leq p_i\leq 10^9$), denoting the price of each book.
Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$), denoting a bidirectional road between $u_i$ and $v_i$. It is guaranteed that the roads form a tree.
In the next $q$ lines, the $i$-th line contains three integers $x_i$, $y_i$ and $z_i$ ($1\leq x_i,y_i\leq n$, $1\leq z_i\leq 10^9$), describing the $i$-th query.
It is guaranteed that the sum of all $n$ is at most $800\,000$, and the sum of all $q$ is at most $800\,000$.
Output
For each query, print a single line containing an integer, denoting the amount of money DreamGrid will have after he checking all the visited books.
1
5 5
5 2 7 4 6
1 2
1 3
2 4
2 5
4 5 10
5 4 10
4 5 12
5 3 12
3 5 11
4
2
0
4
2