Problem Description

Takahashi found a connected undirected graph consisting of $ N $ vertices and $ M $ edges. The vertices are numbered $ 1, 2, ..., N $, and edge $ i $ connects vertex $ a_i $ and vertex $ b_i $. Each edge has a weight, and the weight of edge $ i $ is $ c_i $.

Takahashi decided to play a game $ Q $ times, where in the $ i $-th game, he uses vertices $ S_i $ and $ T_i $. In the $ i $-th game, he wants to choose a subset of edges such that every vertex can be reached from either vertex $ S_i $ or vertex $ T_i $ by traversing only the chosen edges.

For each game, find the minimum possible total weight of the edges Takahashi chooses.

Input Format

The input is given from the 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 Format

Output $ Q $ lines, where the $ i $-th line contains the minimum possible total weight of the edges Takahashi chooses in the $ i $-th game.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8
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

Notes/Hints

Constraints

• $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$
• The graph given in the input is connected.

Partial Points

• For a dataset worth 200 points, $ Q = 1 $ holds.
• For another dataset worth 300 points, $Q \leq 3000$ holds.

Sample Explanation 1

For each game:
- In the 1st game, choosing edges 1 and 3 achieves the minimum value of 8.
- In the 2nd game, choosing edges 1 and 2 achieves the minimum value of 7.

Sample Explanation 2

This input satisfies the constraints for both partial point datasets.

见题面 Input 部分

见题面 Output 部分