#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int root[4001];
int del[4001][4001]={};
int p;
vector<pair<int,int> > graph[4001];
int find(int x){
	if(x != root[x]){
		root[x]=find(root[x]);
	}
	return root[x];
}

void union_set(int x,int y){
	x=find(x);
	y=find(y);
	if(x!=y){
		root[x]=y;
	}
	return;
}

void dfs(int x,int y,int z){
	del[p][x] = z;
	for(int i=0;i<graph[x].size();i++){
		if(graph[x][i].first==y)continue;
		dfs(graph[x][i].first,x,max(z,graph[x][i].second));
	}
}

int main(){
	for(int i=0;i<4001;i++){
		root[i] = i;
	}
	int n,m,q,a,b,s,t,c;
	long long ans=0;
	long long sum=0;
	vector<pair<long long,pair<int,int> > > node,node2;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		pair<long long,pair<int,int> > tmp;
		cin >> a >> b >> c;
		tmp = make_pair(c,make_pair(a,b));
		node.push_back(tmp);
	}
	sort(node.begin(),node.end());
	for(int i=0;i<node.size();i++){
		if(find(node[i].second.first)!=find(node[i].second.second)){
			sum += node[i].first;
			union_set(node[i].second.first,node[i].second.second);
			node2.push_back(node[i]);
			graph[node[i].second.first].push_back(make_pair(node[i].second.second,node[i].first));
			graph[node[i].second.second].push_back(make_pair(node[i].second.first,node[i].first));
		}
	}
	for(p=1;p<=n;p++){
		dfs(p,-1,-1);
	}
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> s >> t;
		ans = sum-del[s][t];
		cout << ans << 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 <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int root[4001];
int del[4001][4001]={};
int p;
vector<pair<int,int> > graph[4001];
int find(int x){
	if(x != root[x]){
		root[x]=find(root[x]);
	}
	return root[x];
}

void union_set(int x,int y){
	x=find(x);
	y=find(y);
	if(x!=y){
		root[x]=y;
	}
	return;
}

void dfs(int x,int y,int z){
	del[p][x] = z;
	for(int i=0;i<graph[x].size();i++){
		if(graph[x][i].first==y)continue;
		dfs(graph[x][i].first,x,max(z,graph[x][i].second));
	}
}

int main(){
	for(int i=0;i<4001;i++){
		root[i] = i;
	}
	int n,m,q,a,b,s,t,c;
	long long ans=0;
	long long sum=0;
	vector<pair<long long,pair<int,int> > > node,node2;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		pair<long long,pair<int,int> > tmp;
		cin >> a >> b >> c;
		tmp = make_pair(c,make_pair(a,b));
		node.push_back(tmp);
	}
	sort(node.begin(),node.end());
	for(int i=0;i<node.size();i++){
		if(find(node[i].second.first)!=find(node[i].second.second)){
			sum += node[i].first;
			union_set(node[i].second.first,node[i].second.second);
			node2.push_back(node[i]);
			graph[node[i].second.first].push_back(make_pair(node[i].second.second,node[i].first));
			graph[node[i].second.second].push_back(make_pair(node[i].second.first,node[i].first));
		}
	}
	for(p=1;p<=n;p++){
		dfs(p,-1,-1);
	}
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> s >> t;
		ans = sum-del[s][t];
		cout << ans << endl;
	}
	return 0;
}
```