//「何らかの全域木からS--Tパス上の辺を取り除いたもの」を考えればよく、実は「MST - (S--Tパス上の最大コストの辺)」が答えになりそう。
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

struct UF {
	int par[4000];
	UF() { for (int i = 0; i < 4000; i++) par[i] = i; }
	int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); }
	void unit(int x, int y) { x = root(x); y = root(y); par[x] = y; }
	bool isSame(int x, int y) { return root(x) == root(y); }
};

struct Edge {
	int from, to, cost;
	Edge(int from, int to, int cost) { this->from = from; this->to = to; this->cost = cost; }
	Edge() {}
	bool operator<(const Edge &r) const { return cost < r.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int n, m, q;
Edges edges;
UF uf;
Graph mst;
int parents[20][4000];
int depth[4000];
int maxScores[20][4000];

void dfs(int p, int v, int ecost, int dep) {
	parents[0][v] = p;
	depth[v] = dep;
	maxScores[0][v] = ecost;
	
	for (int i = 0; i < mst[v].size(); i++) {
		int nv = mst[v][i].to;
		if (nv == p) continue;
		dfs(v, nv, mst[v][i].cost, dep + 1);
	}
}

int maxPath(int u, int v) {
	int ret = 0, i;
	
	if (depth[u] > depth[v]) swap(u, v);
	if (depth[v] > depth[u]) {
		int d = depth[v] - depth[u];
		for (i = 0; i < 20; i++) {
			if ((d >> i) & 1) {
				ret = max(ret, maxScores[i][v]);
				v = parents[i][v];
			}
		}
	}
	if (u == v) { return ret; }
	if (parents[0][u] == parents[0][v]) {
		int res = max(maxScores[0][u], maxScores[0][v]);
		return max(ret, res);
	}
	
	for (i = 19; i > 0; i--) {
		if (parents[i][u] != parents[i][v]) break;
	}
	int res1 = maxPath(parents[i][u], parents[i][v]);
	int res2 = max(maxScores[i][u], maxScores[i][v]);
	int res = max(res1, res2);
	return max(ret, res);
}

signed main() {
	int i, j;
	
	cin >> n >> m;
	for (i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		edges.push_back(Edge(a, b, c));
	}
	sort(edges.begin(), edges.end());
	
	int mstCost = 0;
	mst.resize(n);
	for (i = 0; i < edges.size(); i++) {
		int u = edges[i].from;
		int v = edges[i].to;
		
		if (!uf.isSame(u, v)) {
			uf.unit(u, v);
			mstCost += edges[i].cost;
			mst[u].push_back(Edge(u, v, edges[i].cost));
			mst[v].push_back(Edge(v, u, edges[i].cost));
		}
	}
	
	dfs(0, 0, 0, 0);
	for (i = 1; i < 20; i++) {
		for (j = 0; j < n; j++) {
			parents[i][j] = parents[i - 1][parents[i - 1][j]];
			maxScores[i][j] = max(maxScores[i - 1][j], maxScores[i - 1][parents[i - 1][j]]);
		}
	}
	
	cin >> q;
	for (i = 0; i < q; i++) {
		int s, t;
		cin >> s >> t; s--; t--;
		if (n <= 2) { cout << 0 << endl; continue; }
		int res = maxPath(s, t);
		cout << mstCost - res << endl;
	}
	return 0;
}
### Prompt

In cpp, your task is to solve 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
//「何らかの全域木からS--Tパス上の辺を取り除いたもの」を考えればよく、実は「MST - (S--Tパス上の最大コストの辺)」が答えになりそう。
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

struct UF {
	int par[4000];
	UF() { for (int i = 0; i < 4000; i++) par[i] = i; }
	int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); }
	void unit(int x, int y) { x = root(x); y = root(y); par[x] = y; }
	bool isSame(int x, int y) { return root(x) == root(y); }
};

struct Edge {
	int from, to, cost;
	Edge(int from, int to, int cost) { this->from = from; this->to = to; this->cost = cost; }
	Edge() {}
	bool operator<(const Edge &r) const { return cost < r.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int n, m, q;
Edges edges;
UF uf;
Graph mst;
int parents[20][4000];
int depth[4000];
int maxScores[20][4000];

void dfs(int p, int v, int ecost, int dep) {
	parents[0][v] = p;
	depth[v] = dep;
	maxScores[0][v] = ecost;
	
	for (int i = 0; i < mst[v].size(); i++) {
		int nv = mst[v][i].to;
		if (nv == p) continue;
		dfs(v, nv, mst[v][i].cost, dep + 1);
	}
}

int maxPath(int u, int v) {
	int ret = 0, i;
	
	if (depth[u] > depth[v]) swap(u, v);
	if (depth[v] > depth[u]) {
		int d = depth[v] - depth[u];
		for (i = 0; i < 20; i++) {
			if ((d >> i) & 1) {
				ret = max(ret, maxScores[i][v]);
				v = parents[i][v];
			}
		}
	}
	if (u == v) { return ret; }
	if (parents[0][u] == parents[0][v]) {
		int res = max(maxScores[0][u], maxScores[0][v]);
		return max(ret, res);
	}
	
	for (i = 19; i > 0; i--) {
		if (parents[i][u] != parents[i][v]) break;
	}
	int res1 = maxPath(parents[i][u], parents[i][v]);
	int res2 = max(maxScores[i][u], maxScores[i][v]);
	int res = max(res1, res2);
	return max(ret, res);
}

signed main() {
	int i, j;
	
	cin >> n >> m;
	for (i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		edges.push_back(Edge(a, b, c));
	}
	sort(edges.begin(), edges.end());
	
	int mstCost = 0;
	mst.resize(n);
	for (i = 0; i < edges.size(); i++) {
		int u = edges[i].from;
		int v = edges[i].to;
		
		if (!uf.isSame(u, v)) {
			uf.unit(u, v);
			mstCost += edges[i].cost;
			mst[u].push_back(Edge(u, v, edges[i].cost));
			mst[v].push_back(Edge(v, u, edges[i].cost));
		}
	}
	
	dfs(0, 0, 0, 0);
	for (i = 1; i < 20; i++) {
		for (j = 0; j < n; j++) {
			parents[i][j] = parents[i - 1][parents[i - 1][j]];
			maxScores[i][j] = max(maxScores[i - 1][j], maxScores[i - 1][parents[i - 1][j]]);
		}
	}
	
	cin >> q;
	for (i = 0; i < q; i++) {
		int s, t;
		cin >> s >> t; s--; t--;
		if (n <= 2) { cout << 0 << endl; continue; }
		int res = maxPath(s, t);
		cout << mstCost - res << endl;
	}
	return 0;
}
```