Cho cây n đỉnh, n-1 cạnh có trọng số c ~(c<=10^4)~ mỗi đỉnh đều có và có duy nhất 1 đường đi tới bất kì đỉnh nảo khác.

Cho Q truy vấn Với mỗi truy vấn hãy tính tổng các cạnh trên đường đi từ x đến y

Dòng đầu là số n ( ~n<=10^5~)

~N-1~ dòng tiếp theo mỗi dòng chứa 3 số ~x_i,y_i,c_i~ (~x_i,y_i<=10^5,c_i<=10^4~)

Dòng tiếp theo số truy vấn Q .

~Q~ dòng mỗi dòng chứa 2 số ~x,y~ (~1<=x,y<=n~) truy vấn cần tính

Với mối truy vấn in ra kết quả cần tìm

Ví dụ:

Input

9
1 2 1
1 3 3
2 4 4
2 5 3
3 6 2
4 7 8
5 8 9 
6 9 10
5
7 9
2 8
4 3
6 2
5 7

Output:

28
12
8 
6 
15

Sub1: ~n<=10^3,q<=10^3~(50% số điểm)

Sub2: ~n<=10^5,q<=10^5~(50% số điểm)