A - Graph Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 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 ≦ 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 が成立する。

入力

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

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

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

Score : 700 points

Problem Statement

Takahashi found an undirected connected graph with N vertices and M edges. The vertices are numbered 1 through N. The i-th edge connects vertices a_i and b_i, and has a weight of c_i.

He will play Q rounds of a game using this graph. In the i-th round, two vertices S_i and T_i are specified, and he will choose a subset of the edges such that any vertex can be reached from at least one of the vertices S_i or T_i by traversing chosen edges.

For each round, find the minimum possible total weight of the edges chosen by Takahashi.

Constraints

  • 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
  • The given graph is connected.

Partial Scores

  • In the test set worth 200 points, Q = 1.
  • In the test set worth another 300 points, Q ≦ 3000.

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines. The i-th line should contain the minimum possible total weight of the edges chosen by Takahashi.

Sample Input 1

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

Sample Output 1

8
7

We will examine each round:

  • In the 1-st round, choosing edges 1 and 3 achieves the minimum total weight of 8.
  • In the 2-nd round, choosing edges 1 and 2 achieves the minimum total weight of 7.

Sample Input 2

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

Sample Output 2

8

This input satisfies the additional constraints for both partial scores.