Description

The $N$ cows ($2 \le N \le 1,000$), conveniently numbered $1$…$N$, are grazing among the $N$ pastures also conveniently numbered $1$…$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 so 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. Being in a hurry, they want you to help schedule their visits by computing the lengths of the paths for $Q$ pairs of pastures ($1 < Q < 1,000$). Each pair is given as a query $p1$, $p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Input Format

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

Output Format

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

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

2 
7 

Hint

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

Translated by ChatGPT 5