#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### graph2

### 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`, and has a weight of

_{i}`c`.

_{i}He will play `Q` rounds of a game using this graph. In the `i`-th round, two vertices `S _{i}` and

`T`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

_{i}`S`or

_{i}`T`by traversing chosen edges.

_{i}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}≠ b_{i}`S`_{i}≠ T_{i}- 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:

NMa_{1}b_{1}c_{1}a_{2}b_{2}c:_{2}a_{M}b_{M}c_{M}QS_{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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 28 | 11 | 3s | 256MB | Minimum |

2 | 43 | 8 | 3s | 256MB | Minimum |

3 | 29 | 29 | 3s | 256MB | Minimum |

4 | 0 | 2 | 3s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o graph2 -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512