#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;
const string nyan("(=^・ω・^=)");

int N, M, Q, S, T, a, b, c, uf[4000], r[4000], d[4000][2][15];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>>q;
vector<pair<int, int>>v[4000];
ll e;

int t(int x) {
	if (uf[x] < 0)return x;
	return uf[x] = t(uf[x]);
}

bool u(int x, int y) {
	x = t(x);
	y = t(y);
	if (x == y)return false;
	if (uf[x] < uf[y]) {
		uf[x] += uf[y];
		uf[y] = x;
	}
	else {
		uf[y] += uf[x];
		uf[x] = y;
	}
	return true;
}

void dfs(int x) {
	for (auto p : v[x]) {
		if (!r[p.second]) {
			r[p.second] = r[x] + 1;
			d[p.second][0][0] = p.first;
			d[p.second][1][0] = x;
			dfs(p.second);
		}
	}
}

int calc(int x, int y) {
	int m = 0;
	if (r[x] < r[y]) {
		for (int i = 14; i >= 0; --i) {
			if (r[x] + (1 << i) <= r[y]) {
				m = max(m, d[y][0][i]);
				y = d[y][1][i];
			}
		}
	}
	if (r[x] > r[y]) {
		for (int i = 14; i >= 0; --i) {
			if (r[y] + (1 << i) <= r[x]) {
				m = max(m, d[x][0][i]);
				x = d[x][1][i];
			}
		}
	}
	if (x != y) {
		for (int i = 14; i >= 0; --i) {
			if (d[x][1][i] != d[y][1][i]) {
				m = max(m, d[x][0][i]);
				m = max(m, d[y][0][i]);
				x = d[x][1][i];
				y = d[y][1][i];
			}
		}
		m = max(m, d[x][0][0]);
		m = max(m, d[y][0][0]);
	}
	return m;
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		cin >> a >> b >> c;
		q.push(mkp(c, mkp(a - 1, b - 1)));
	}
	memset(uf, -1, sizeof uf);
	while (!q.empty()) {
		if (u(q.top().second.first, q.top().second.second)) {
			v[q.top().second.first].push_back(mkp(q.top().first, q.top().second.second));
			v[q.top().second.second].push_back(mkp(q.top().first, q.top().second.first));
			e += q.top().first;
		}
		q.pop();
	}
	r[0] = 1;
	dfs(0);
	for (int i = 0; i < 14; ++i) {
		for (int j = 0; j < N; ++j) {
			d[j][0][i + 1] = max(d[j][0][i], d[d[j][1][i]][0][i]);
			d[j][1][i + 1] = d[d[j][1][i]][1][i];
		}
	}
	cin >> Q;
	while (Q--) {
		cin >> S >> T;
		cout << e - calc(S - 1, T - 1) << endl;
	}
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;
const string nyan("(=^・ω・^=)");

int N, M, Q, S, T, a, b, c, uf[4000], r[4000], d[4000][2][15];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>>q;
vector<pair<int, int>>v[4000];
ll e;

int t(int x) {
	if (uf[x] < 0)return x;
	return uf[x] = t(uf[x]);
}

bool u(int x, int y) {
	x = t(x);
	y = t(y);
	if (x == y)return false;
	if (uf[x] < uf[y]) {
		uf[x] += uf[y];
		uf[y] = x;
	}
	else {
		uf[y] += uf[x];
		uf[x] = y;
	}
	return true;
}

void dfs(int x) {
	for (auto p : v[x]) {
		if (!r[p.second]) {
			r[p.second] = r[x] + 1;
			d[p.second][0][0] = p.first;
			d[p.second][1][0] = x;
			dfs(p.second);
		}
	}
}

int calc(int x, int y) {
	int m = 0;
	if (r[x] < r[y]) {
		for (int i = 14; i >= 0; --i) {
			if (r[x] + (1 << i) <= r[y]) {
				m = max(m, d[y][0][i]);
				y = d[y][1][i];
			}
		}
	}
	if (r[x] > r[y]) {
		for (int i = 14; i >= 0; --i) {
			if (r[y] + (1 << i) <= r[x]) {
				m = max(m, d[x][0][i]);
				x = d[x][1][i];
			}
		}
	}
	if (x != y) {
		for (int i = 14; i >= 0; --i) {
			if (d[x][1][i] != d[y][1][i]) {
				m = max(m, d[x][0][i]);
				m = max(m, d[y][0][i]);
				x = d[x][1][i];
				y = d[y][1][i];
			}
		}
		m = max(m, d[x][0][0]);
		m = max(m, d[y][0][0]);
	}
	return m;
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		cin >> a >> b >> c;
		q.push(mkp(c, mkp(a - 1, b - 1)));
	}
	memset(uf, -1, sizeof uf);
	while (!q.empty()) {
		if (u(q.top().second.first, q.top().second.second)) {
			v[q.top().second.first].push_back(mkp(q.top().first, q.top().second.second));
			v[q.top().second.second].push_back(mkp(q.top().first, q.top().second.first));
			e += q.top().first;
		}
		q.pop();
	}
	r[0] = 1;
	dfs(0);
	for (int i = 0; i < 14; ++i) {
		for (int j = 0; j < N; ++j) {
			d[j][0][i + 1] = max(d[j][0][i], d[d[j][1][i]][0][i]);
			d[j][1][i + 1] = d[d[j][1][i]][1][i];
		}
	}
	cin >> Q;
	while (Q--) {
		cin >> S >> T;
		cout << e - calc(S - 1, T - 1) << endl;
	}
}
```