問題文

$N$ 頂点 $N$ 辺の単純かつ連結な無向グラフが与えられます。 このグラフの $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を相互に結び、長さは $C_i$ です。

このグラフ上の最短路クエリが $Q$ 個与えられるので、これに答えてください。 $j$ 番目のクエリでは頂点 $X_j$ と頂点 $Y_j$ の間の最短路を求めてください。

制約

• $3 \le N \le 2\times 10^5$
• $1 \le A_i, B_i \le N$
• $1 \le C_i \le 10^{12}$
• $1 \le Q \le 2\times 10^5$
• $1 \le X_j, Y_j \le N$
• 入力はすべて整数である

入力

出力

$Q$ 行出力してください。 $j = 1, 2, \ldots, Q$ について、 $j$ 行目には $j$ 番目のクエリに対する答えを出力してください。

入出力例

4 3
1 2 1
1 3 2
3 4 4
4 1 8
1 2
1 4
4 2

1
6
7

11 6
1 5 1
7 5 2
1 7 4
2 1 8
2 4 16
3 2 32
5 6 64
8 7 128
9 7 256
9 10 512
11 9 1024
1 7
3 6
11 8
11 10
4 10
6 9

3
105
1408
1536
795
322

10 10
10 7 508252356070
10 4 328974562802
9 1 885368849936
9 10 580933898755
9 5 349344869736
1 6 394235217277
10 3 21578149681
1 2 19279158318
6 4 803839369377
9 8 982198770298
1 6
8 2
1 4
1 7
7 6
6 10
5 7
4 3
10 2
4 8

394235217277
1886846778552
1198074586654
1974555104761
1641066288249
1132813932179
1438531124561
350552712483
1485581907009
1892107231855