#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)



typedef long long ll;
template<int um> class UF { // from kmjp
public:
	vector<int> par;
	UF() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; }
	int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
	void operator()(int x, int y)
	{
		x = operator[](x); y = operator[](y);
		if (x != y) par[x] = y;
	}
};
//-----------------------------------------------------------------
int N, M;
tuple<int, int, int> buf[404040];
int D[4040][4040];
UF<4040> uf;
vector<pair<int, int>> E[4040];
//-----------------------------------------------------------------
void dfs(int st, int cur, int par, int ma) {
	D[st][cur] = ma;

	for (auto p : E[cur]) if (p.first != par) dfs(st, p.first, cur, max(ma, p.second));
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		buf[i] = make_tuple(c, a, b);
	}
	sort(buf, buf + M);

	ll sm = 0;
	rep(i, 0, M) {
		int a = get<1>(buf[i]);
		int b = get<2>(buf[i]);
		int c = get<0>(buf[i]);

		if (uf[a] != uf[b]) {
			uf(a, b);
			E[a].push_back(make_pair(b, c));
			E[b].push_back(make_pair(a, c));
			sm += c;
		}
	}

	rep(i, 1, N + 1) dfs(i, i, -1, 0);

	int Q; cin >> Q;
	rep(i, 0, Q) {
		int s, t;
		scanf("%d %d", &s, &t);

		ll ans = sm - D[s][t];
		printf("%lld\n", ans);
	}
}
### Prompt

Please create a solution in CPP to the following problem:

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.

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.

Examples

Input

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


Output

8
7


Input

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


Output

8

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)



typedef long long ll;
template<int um> class UF { // from kmjp
public:
	vector<int> par;
	UF() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; }
	int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
	void operator()(int x, int y)
	{
		x = operator[](x); y = operator[](y);
		if (x != y) par[x] = y;
	}
};
//-----------------------------------------------------------------
int N, M;
tuple<int, int, int> buf[404040];
int D[4040][4040];
UF<4040> uf;
vector<pair<int, int>> E[4040];
//-----------------------------------------------------------------
void dfs(int st, int cur, int par, int ma) {
	D[st][cur] = ma;

	for (auto p : E[cur]) if (p.first != par) dfs(st, p.first, cur, max(ma, p.second));
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		buf[i] = make_tuple(c, a, b);
	}
	sort(buf, buf + M);

	ll sm = 0;
	rep(i, 0, M) {
		int a = get<1>(buf[i]);
		int b = get<2>(buf[i]);
		int c = get<0>(buf[i]);

		if (uf[a] != uf[b]) {
			uf(a, b);
			E[a].push_back(make_pair(b, c));
			E[b].push_back(make_pair(a, c));
			sm += c;
		}
	}

	rep(i, 1, N + 1) dfs(i, i, -1, 0);

	int Q; cin >> Q;
	rep(i, 0, Q) {
		int s, t;
		scanf("%d %d", &s, &t);

		ll ans = sm - D[s][t];
		printf("%lld\n", ans);
	}
}
```