### ** 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 `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} ≠ 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:

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