問題文

$N$ 頂点の重み付き無向木が与えられます。$i(1 \le i \le N - 1)$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ をコスト $c_i$ で結びます。
$Q$ 個の質問に対して、$j(1 \le j \le Q)$ 番目の質問では頂点 $s_j$ から頂点 $t_j$ までの最小コストを答えてください。

入力

$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$ は頂点 $a_i$ と頂点 $b_i$ をコスト $c_i$ で結ぶ辺があることを表す。
$1 \le a_i, b_i, s_j, t_j \le N$
$1 \le c_i \le 10^4$
入力はすべて整数。
入力は木

出力

改行区切りで $Q$ 行にわたって答えを出力せよ。最後に改行せよ。

サンプル

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