Trams of Berlin P51603

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⁵, that tram stops are numbered starting at 0, 1 ≤ ℓ ≤ 10⁹, 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.