Problem Statement

You are given a weighted undirected tree with $N$ vertices. The $i(1 \le i \le N - 1)$-th edge connects vertex $a_i$ and vertex $b_i$ with cost $c_i$.
For $Q$ queries, in the $j(1 \le j \le Q)$-th query, answer the minimum cost from vertex $s_j$ to vertex $t_j$.

Input

$N$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$\dots$
$a_{N-1}\ b_{N-1}\ c_{N-1}$
$Q$
$s_1\ t_1$
$s_2\ t_2$
$\dots$
$s_Q\ t_Q$

$1 \le N, Q \le 2 \times 10^5$
$a_i, b_i, c_i$ indicate that there is an edge connecting vertex $a_i$ and vertex $b_i$ with cost $c_i$.
$1 \le a_i, b_i, s_j, t_j \le N$
$1 \le c_i \le 10^4$
All inputs are integers.
The input is a tree.

Output

Output the answers over $Q$ lines, separated by newlines. Print a newline at the end.

Sample

5
1 2 1
2 3 10
1 4 100
2 5 1000
6
1 2
1 5
2 4
1 4
5 3
1 1

1
1001
101
100
1010
0