题目描述

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

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

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

输入格式

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

$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$ 回目のゲームにおいて高橋君が選ぶ辺の重みの総和として考えられる最小値を出力せよ。

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

8
7

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

8

提示

制約

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

部分点

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

Sample Explanation 1

各ゲームについて見ると、 - $1$ 回目のゲームでは辺 $1$ と辺 $3$ を選ぶことで、最小値 $8$ が達成されます。 - $2$ 回目のゲームでは辺 $1$ と辺 $2$ を選ぶことで、最小値 $7$ が達成されます。

Sample Explanation 2

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