#include <bits/stdc++.h>
#define int long long
using namespace std;

struct edge{ int from,to,cost; };

int par[4010],rnk[4010];

int find(int x){
	if(x == par[x]) return x;
	return par[x] = find(par[x]);
}

void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rnk[x] < rnk[y]) par[x] = y;
	else{
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
}

bool same(int a,int b){
	return find(a) == find(b);
}

int ma[4000][4000];
vector<edge> G[4000],vec;

void dfs(int v,int par,int r){
	for(edge e : G[v]){
		if(e.to != par){
			ma[e.to][r] = max(ma[v][r],e.cost);
			dfs(e.to,v,r);
		}
	}
}

signed main(){
	int n,m,q,sum = 0;
	cin >> n >> m;
	for(int i = 0;i < n;i++){
		rnk[i] = 0;
		par[i] = i;
	}
	for(int i = 0;i < m;i++){
		int a,b,c;
		cin >> a >> b >> c; a--;b--;
		vec.push_back({a,b,c});
	}
	sort(vec.begin(),vec.end(),[](const edge a,const edge b){ return a.cost < b.cost; });
	for(edge e : vec){
		if(!same(e.from,e.to)){
			unite(e.from,e.to);
			sum += e.cost;
			G[e.from].push_back(e);
			G[e.to].push_back({e.to,e.from,e.cost});
		}
	}
	for(int i = 0;i < n;i++) dfs(i,-1,i);
	cin >> q;
	for(int i = 0;i < q;i++){
		int s,t;
		cin >> s >> t; s--;t--;
		cout << sum - ma[s][t] << endl;
	}
	return 0;
}
### 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>
#define int long long
using namespace std;

struct edge{ int from,to,cost; };

int par[4010],rnk[4010];

int find(int x){
	if(x == par[x]) return x;
	return par[x] = find(par[x]);
}

void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rnk[x] < rnk[y]) par[x] = y;
	else{
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
}

bool same(int a,int b){
	return find(a) == find(b);
}

int ma[4000][4000];
vector<edge> G[4000],vec;

void dfs(int v,int par,int r){
	for(edge e : G[v]){
		if(e.to != par){
			ma[e.to][r] = max(ma[v][r],e.cost);
			dfs(e.to,v,r);
		}
	}
}

signed main(){
	int n,m,q,sum = 0;
	cin >> n >> m;
	for(int i = 0;i < n;i++){
		rnk[i] = 0;
		par[i] = i;
	}
	for(int i = 0;i < m;i++){
		int a,b,c;
		cin >> a >> b >> c; a--;b--;
		vec.push_back({a,b,c});
	}
	sort(vec.begin(),vec.end(),[](const edge a,const edge b){ return a.cost < b.cost; });
	for(edge e : vec){
		if(!same(e.from,e.to)){
			unite(e.from,e.to);
			sum += e.cost;
			G[e.from].push_back(e);
			G[e.to].push_back({e.to,e.from,e.cost});
		}
	}
	for(int i = 0;i < n;i++) dfs(i,-1,i);
	cin >> q;
	for(int i = 0;i < q;i++){
		int s,t;
		cin >> s >> t; s--;t--;
		cout << sum - ma[s][t] << endl;
	}
	return 0;
}
```