Pasture Walking

There are $N$ cows ($2 \le N \le 1{,}000$), conveniently numbered $1..N$, grazing among $N$ pastures that are also numbered $1..N$. Most conveniently of all, cow $i$ is grazing in pasture $i$.

Some pairs of pastures are connected by bidirectional walkways that the cows can traverse, and there are $N-1$ walkways in total. Walkway $i$ connects pastures $A_i$ and $B_i$ ($1 \le A_i \le N$, $1 \le B_i \le N$) and has length $L_i$ ($1 \le L_i \le 10{,}000$).

The walkways are arranged so that between any two distinct pastures there is exactly one path of walkways. In other words, the walkways form a tree.

The cows are very social and want to visit one another often. For $Q$ pairs of pastures ($1 \le Q \le 1{,}000$), each given as a query $p_1, p_2$ ($1 \le p_1 \le N$, $1 \le p_2 \le N$, $p_1 \ne p_2$), compute the length of the path connecting them.

• Line 1: Two space-separated integers $N$ and $Q$.
• Lines 2 to $N$: Line $i+1$ contains three space-separated integers $A_i$, $B_i$, and $L_i$.
• Lines $N+1$ to $N+Q$: Each line contains two space-separated integers $p_1$ and $p_2$, the two distinct pastures the cows wish to travel between.

• For each query $i$, print on line $i$ the length of the path between the two pastures given in that query. ($Q$ lines in total.)

• First query: the walkway between pastures $1$ and $2$ has length $2$.
• Second query: travel along 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$.