$N$ 個の頂点と $M$ 本の辺を持つ、単純な無向重み付き連結グラフが与えられる。

2つの頂点 $s$ と $e$ の間の最短距離を求めるクエリを $Q$ 回処理せよ。

入力

1行目に頂点数 $N$ と辺の数 $M$ が空白区切りで与えられる。 $(1 \le N \le 10^{5}; N-1 \le M \le N+50)$

2行目から $M$ 行にわたり、各行に辺が結ぶ2つの頂点 $u, v$ とその辺の重み $w$ が空白区切りで与えられる。 $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^{9})$

$M+2$ 行目にクエリの数 $Q$ が与えられる。 $(1 \le Q \le 10^{5})$

$M+3$ 行目から $Q$ 行にわたり、各行に最短距離を求めるべき2つの頂点 $s, e$ が空白区切りで与えられる。 $(1 \le s, e \le N)$

出力

1行目から $Q$ 行にわたり、各行に頂点 $s$ から頂点 $e$ までの最短距離を出力せよ。

入出力例

入力 1

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

出力 1

2
4

入力 2

6 8
1 2 1
3 1 2
2 3 2
5 2 1
3 5 4
5 4 5
2 6 3
4 2 3
4
1 6
4 1
5 5
6 3

出力 2

4
4
0
5