#include <bits/stdc++.h>
using namespace std;
const int maxn = 4040;
int uf[maxn];
int find(int x){
	if(x == uf[x]) return x;
	return uf[x] = find(uf[x]);
}
vector<pair<int,int> > e[maxn];
int dep[maxn], par[maxn], cost[maxn];
void dfs(int u){
	for(auto to : e[u]){
		if(to.first == par[u]) continue;
		dep[to.first] = dep[u] + 1;
		cost[to.first] = to.second;
		par[to.first] = u;
		dfs(to.first);
	}
}
int main(){
	iota(uf, uf + maxn, 0);
	int n, m; cin >> n >> m;
	vector<tuple<int,int,int> > eds;
	for(int i = 0; i < m; i++){
		int u, v, w; cin >> u >> v >> w;
		eds.push_back(make_tuple(w, u, v));
	}
	sort(eds.begin(), eds.end());
	long long mst = 0;
	for(int i = 0; i < m; i++){
		int u, v, w; tie(w, u, v) = eds[i];
		if(find(u) != find(v)){
			e[u].push_back({v, w});
			e[v].push_back({u, w});
			mst += w;
			uf[find(u)] = find(v);
		}
	}
	dfs(1);
	int q; scanf("%d", &q);
	for(int i = 0; i < q; i++){
		int s, t; cin >> s >> t;
		int big = 0;
		while(s != t){
			if(dep[s] < dep[t]) swap(s, t);
			big = max(big, cost[s]);
			s = par[s];
		}
		printf("%lld\n", mst - big);
	}
	return 0;
}

### Prompt

Develop a solution in Cpp 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>
using namespace std;
const int maxn = 4040;
int uf[maxn];
int find(int x){
	if(x == uf[x]) return x;
	return uf[x] = find(uf[x]);
}
vector<pair<int,int> > e[maxn];
int dep[maxn], par[maxn], cost[maxn];
void dfs(int u){
	for(auto to : e[u]){
		if(to.first == par[u]) continue;
		dep[to.first] = dep[u] + 1;
		cost[to.first] = to.second;
		par[to.first] = u;
		dfs(to.first);
	}
}
int main(){
	iota(uf, uf + maxn, 0);
	int n, m; cin >> n >> m;
	vector<tuple<int,int,int> > eds;
	for(int i = 0; i < m; i++){
		int u, v, w; cin >> u >> v >> w;
		eds.push_back(make_tuple(w, u, v));
	}
	sort(eds.begin(), eds.end());
	long long mst = 0;
	for(int i = 0; i < m; i++){
		int u, v, w; tie(w, u, v) = eds[i];
		if(find(u) != find(v)){
			e[u].push_back({v, w});
			e[v].push_back({u, w});
			mst += w;
			uf[find(u)] = find(v);
		}
	}
	dfs(1);
	int q; scanf("%d", &q);
	for(int i = 0; i < q; i++){
		int s, t; cin >> s >> t;
		int big = 0;
		while(s != t){
			if(dep[s] < dep[t]) swap(s, t);
			big = max(big, cost[s]);
			s = par[s];
		}
		printf("%lld\n", mst - big);
	}
	return 0;
}

```