The $N$ cows $(2 \le N \le 1,000)$ conveniently numbered $1,\ldots,N$ are grazing among the $N$ pastures also conveniently numbered $1,\ldots,N$. Most conveniently of all, cow $i$ is grazing in pasture $i$.

Some pairs of pastures are connected by one of $N-1$ bidirectional walkways that the cows can traverse. Walkway $i$ connects pastures $A_{i}$ and $B_{i}$ $(1 \le A_{i} \le N; 1 \le B_{i} \le N)$ and has a length of $L_{i}$ $(1 \le L_{i} \le 10,000)$.

The walkways are set up in such a way that between any two distinct pastures, there is exactly one path of walkways that travels between them. Thus, the walkways form a tree.

The cows are very social and wish to visit each other often. Ever in a hurry, they want you to help them schedule their visits by computing the lengths of the paths between $Q$ $(1 \le Q \le 1,000)$ pairs of pastures (each pair given as a query $p1,p2$ $(1 \le p1 \le N; 1 \le p2 \le N)$.

Input

• Line 1: Two space-separated integers: $N$ and $Q$
• Lines $2,\ldots,N$: Line $i+1$ contains three space-separated integers: $A_{i}$, $B_{i}$, and $L_{i}$
• Lines N+$1,\ldots,N+Q$: Each line contains two space-separated integers representing two distinct pastures between which the cows wish to travel: $p1$ and $p2$

Output

• Lines $1,\ldots,Q$: Line $i$ contains the length of the path between the two pastures in query $i$.

Examples

Input 1

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Output 1

2
7

Query 1: The walkway between pastures 1 and 2 has length 2. Query 2: Travel through the walkway between pastures 3 and 4, then the one between 4 and 1, and finally the one between 1 and 2, for a total length of 7.

Scoring

POINTS: 200

Problem credits: Neal Wu, 2007