Baq is living in Berlin, a city really well connected thanks to its great public transport service. In particular, it has quite a vast tram network, with a peculiar characteristic: between any two tram stops, there is exactly one route that connects them.

Baq has made a lot of friends in the city,
and they are going to meet him soon, each on a different day.
For each meeting i, let x_{i} and y_{i} be the tram stops
where Baq and his i-th friend plan to be before the meeting, respectively.
They will meet halfway, that is,
at the stop that falls closer to the middle point
following the route that connects x_{i} and y_{i}.
In case of a tie, they will choose the tram stop closer to Baq.
Can you efficiently compute the total distance travelled by each of Baq’s friends?

Input

Input consists of several cases.
Every case begins with the number of tram stops n.
Follow n−1 triples x y ℓ describing a street of length ℓ connecting x and y.
Follow n queries x_{i} y_{i}.
Assume 2 ≤ n ≤ 10^{5},
that tram stops are numbered starting at 0,
1 ≤ ℓ ≤ 10^{9},
that the given streets form a tree,
and that the queries are all different.

Output

For each case, print the total distance of the travel of every Baq’s friend. Print a line with 10 dashes at the end of each case.

Public test cases

**Input**

2 1 0 100 0 1 1 1 7 0 1 999999999 2 1 1000000000 6 3 1 4 3 1000000000 5 4 999999998 0 3 1000000000 1 0 0 2 2 0 3 6 2 5 5 2 2 6

**Output**

100 0 ---------- 999999999 1000000000 999999999 1 2999999998 1999999999 1000000001 ----------

Information

- Author
- Víctor Martín
- Language
- English
- Official solutions
- C++
- User solutions
- C++