Andy the goat has a get rich quick scheme! He will get a job at Hoptiver, the most prestigious Quant firm in Australia. But there is a slight problem: he did not submit the OA and therefore got rejected. Andy does not give up, however, because he has his eyes on a bigger prize - the CEO position.

Now that Andy is the CEO of Hoptiver, he wants to become filthy rich. Hoptiver makes their money by moving their stock positions, and he soon discovers Hoptiver has ~n~ of these and ~n-1~ connections between them. Furthermore, every position can reach every other position. Each connection has an amount of profit associated with it.

As a smart goat, Andy has ~q~ questions about this process. Each question is of the form ~a b~, meaning that he wants to know if he starts at position ~a~ and takes the shortest path to get to position ~b~, what is the amount of profit he will make? As the farmer who owns Andy the goat (do farmers own goats? idk), help him with these questions so you can share in the profits!

Input Format

The first line will contain two integers, ~n~ and ~q~. The next ~n-1~ lines each contain 3 integers: ~a b c~, meaning that position ~a~ can reach position ~b~ with ~c~ profit, and vice versa. Finally the next ~q~ lines contain two integers ~a~ and ~b~ each, representing one of his questions.

Output Format

The output should consist of ~q~ lines, the i-th of which containing the answer to Andy's i-th question.

Example Input 1

3 2
0 1 5
0 2 6
0 1
1 2

Example Output 1

5
11

Example Explanation

The first query asks for the path from 0 to 1, which contains a single profit 5. The second query asks for the path from 1 to 2, which contains the two profits 5 and 6, therefore the answer is 11.

Constraints

~2 \le N \le 10^5~

~1 \le Q \le 10^5~

The profits are ~\le 100~

The positions have names ~0,1..(n-1)~