The N cows (2 <= N <= 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 Ai and Bi (1 <= Ai <= N; 1 <= Bi <= N) and has a length of Li (1 <= Li <= 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 1 <= Li <= 10,000 pairs of pastures (each pair given as a query p1,p2 (1 <= p1 <= N; 1 <= p2 <= N).
POINTS: 200

* Line 1: Two space-separated integers: N and Q
* Lines 2..N: Line i+1 contains three space-separated integers: Ai, Bi, and Li
* 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

* 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

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.