The link to the Russian translation.

Enzo is trying to reach Bonnie in her dream. Bonnie's dreamland is so big. It has n cities and n-1 roads. One can go from any city to any other city using only these roads. So, it means there's a unique shortest path between any two cities. Each road has an integer length.

For a sequence of integers a1, a2, ..., ak, sum(l, r) = al + al+1 + ... + ar-1 (1 ≤ l ≤ r ≤ k+1, so by definition sum(x, x) = 0).

prettiness(al + al+1 + ... + ar-1) = max(sum(l, r)) for 1 ≤ l ≤ r ≤ k+1.

Enzo is too mysterious and curious, he has q questions (for what, we don't know). You're his only programmer friend, so he asks you the questions. In each question he gives you v and u and you should tell him the value of goodness(v, u) which can be calculated as follows: suppose e1, e2, ..., ek are the roads on the shortest path from v to u , in order we see them when we go from v to u (if v = u, then k = 0). goodness(v, u) = prettiness(length(e1), length(e2), ..., length(ek)).

Input
The first line of input contains two integers n and q (1 ≤ n, q ≤ 10^5).

The next n-1 lines contain the roads. Each line contains 3 integers v, u, w meaning there is a road between v and u with length equal to w (1 ≤ v, u ≤ n, v ≠ u, |w| ≤ 10^9).

The next q lines contain the questions. Each contains two integers v and u (1 ≤ v, u ≤ n).

Output
Print the answer to each question in one line.

SAMPLE INPUT
7 10
1 2 -4
5 4 -2
5 1 10
2 7 8
3 6 7
7 6 9
7 1
1 2
4 3
5 5
3 4
5 7
7 5
1 1
3 7
1 6

SAMPLE OUTPUT
8
0
30
0
30
14
14
0
16
17

见题面

见题面