Problem Description
Alice and Bob are playing games again! This time, they invent a new game called "Color the Tree". They draw a tree with N nodes and, certainly, (N-1) edges connecting them to assure a path between each pair of the nodes. But the tree they play with is a little special - each edge is assigned to a color and a specific value. Initially, the value of each edge is settled while the colors are all white.
When the game starts, Alice and Bob each choose a node as her/his starting node. In each round, Alice firstly makes a move from her current node to another through an edge with a color of white or red, and if the edge is white, she colors it to red. After that, Bob makes a similar move through a white or blue edge from his current node, and if the edge is white, he colors it to blue. The game keeps going on until all the edges are colored to either red or blue.
Alice's goal is to maximize the sum of values of the red edges, and Bob, wants to maximize that of the blue edges. Given the starting node of them, figure out the maximum sum that Alice is able to obtain if both of them take the best strategy in each round.
Input
The first line of the input contains a single integer T, indicating there are T test cases.
In each case, the first line contains two integers N and M, which denotes the number of nodes and queries.
Each of the following (N-1) lines contains a triple of integers (a,b,c), indicating there is an edge connecting node a and node b with a value of c.
The following M lines describe the queries. Each of the M lines consists of two integers A and B, indicating the starting node of Alice and Bob, respectively.
(2≤N≤100000,1≤M≤100000,1≤a,b,A,B≤N,1≤c≤1000)
Output
For each query, output the maximum sum that Alice can obtain, one per line.
Sample Input
2
2 1
1 2 3
1 2
3 2
1 2 3
1 3 1
2 3
1 3
Sample Output
3
3
4
