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

The first line contains two integers ~n~ and ~q~.

The next ~n-1~ lines each contain three integers ~a~, ~b~, and ~c~, meaning that position ~a~ can reach position ~b~ with profit ~c~, and vice versa.

Finally, the next ~q~ lines each contain two integers ~a~ and ~b~, representing one of Andy's questions.

Output

Output ~q~ lines. The ~i~-th line should contain the answer to Andy's ~i~-th question.

Constraints

• ~2 \le n \le 10^5~
• ~1 \le q \le 10^5~
• ~0 \le a, b \le n-1~
• ~1 \le c \le 100~
• The positions are labelled ~0, 1, \ldots, n-1~
• The connections form a tree (every position can reach every other position)

Example 1

Input

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

Output

5
11

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~.