配点 : $700$ 点

問題文

高橋君は $N$ 頂点 $M$ 辺からなる連結な無向グラフを見つけました。頂点には $1,2,...,N$ の番号がついており、辺 $i$ は頂点 $a_i$ と頂点 $b_i$ をつないでいます。また、辺には重さがあり、辺 $i$ の重さは $c_i$ です。

そこで、高橋君は $Q$ 回ゲームをし、 $i$ 回目のゲームで頂点 $S_i$ と頂点 $T_i$ を使うことにしました。$i$ 回目のゲームでは辺の部分集合を選び、どの頂点にも頂点 $S_i$ または頂点 $T_i$ から選ばれた辺のみをたどってたどり着けるようにしたいです。

各ゲームにおいて、高橋君が選ぶ辺の重みの総和として考えられる最小値を求めてください。

制約

• $1 \leq N \leq 4,000$
• $1 \leq M \leq 400,000$
• $1 \leq Q \leq 100,000$
• $1 \leq a_i,b_i,S_i,T_i \leq N$
• $1 \leq c_i \leq 10^{9}$
• $a_i \neq b_i$
• $S_i \neq T_i$
• 入力で与えられるグラフは連結である。

部分点

• $200$ 点分のデータセットでは、$Q = 1$ が成立する。
• 別の $300$ 点分のデータセットでは、$Q \leq 3000$ が成立する。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$a_1$ $b_1$ $c_1$

$a_2$ $b_2$ $c_2$

$:$

$a_M$ $b_M$ $c_M$

$Q$

$S_1$ $T_1$

$S_2$ $T_2$

$:$

$S_Q$ $T_Q$

出力

$Q$ 行出力し、$i$ 行目には $i$ 回目のゲームにおいて高橋君が選ぶ辺の重みの総和として考えられる最小値を出力せよ。

入力例1

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

出力例1

8
7

各ゲームについて見ると、

• $1$ 回目のゲームでは辺 $1$ と辺 $3$ を選ぶことで、最小値 $8$ が達成されます。
• $2$ 回目のゲームでは辺 $1$ と辺 $2$ を選ぶことで、最小値 $7$ が達成されます。

入力例2

4 6
1 3 5
4 1 10
2 4 6
3 2 2
3 4 5
2 1 3
1
2 3

出力例2

8

この入力はどちらの部分点の制約も満たします。