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 a₁, a₂, ..., a_k, sum(l, r) = a_l + a_l+1 + ... + a_r-1 (1 ≤ l ≤ r ≤ k+1, so by definition sum(x, x) = 0).

prettiness(a_l + a_l+1 + ... + a_r-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 e₁, e₂, ..., e_k 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(e₁), length(e₂), ..., length(e_k)).

Input

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

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⁹).

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.