graph

graph

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 ai and bi, and has a weight of ci.

He will play Q rounds of a game using this graph. In the i-th round, two vertices Si and Ti 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 Si or Ti 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 ≦ ai,bi,Si,Ti ≦ N
  • 1 ≦ ci ≦ 109
  • ai ≠ bi
  • Si ≠ Ti
  • The given graph is connected.

Partial Scores

  • In the test set worth 28 points, Q = 1.
  • In the test set worth another 43 points, Q ≦ 3000.

Input

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

N M
a1 b1 c1
a2 b2 c2
:
aM bM cM
Q
S1 T1
S2 T2
:
SQ TQ

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.


Compile Errors


							
Time Limit: 3 Seconds
Memory Limit: 1024MB
No. of ACs: 3
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 28
2 43
3 29
4 0