#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 100000000

struct unionfind{
	vector<int> data;
	vector<int> size;
	unionfind(int n){
		for(int i=0;i<n;i++){
			data.push_back(i);
			size.push_back(1);
		}
	}
	
	int find(int x){
		if(data[x]==x)return x;
		return data[x]=find(data[x]);
	}
	
	bool unite(int x,int y){
		x=find(x);y=find(y);
		if(x==y)return false;
		data[x]=y;
		size[y]+=size[x];
		return true;
	}
	
	bool check(int x,int y){
		return (find(x)==find(y));
	}
	
	int get_size(int x){
		int X = find(x);
		return size[X];
	}
};


void dfs(vector<vector<long long>> &ans,vector<vector<pair<int,long long>>> &E,int now,int parent,int first,long long maxi){
	
	ans[first][now] = maxi;
	
	for(int i=0;i<E[now].size();i++){
		int to = E[now][i].first;
		long long c = E[now][i].second;
		if(to==parent)continue;
		dfs(ans,E,to,now,first,max(maxi,c));
	}
	
}


int main(){
	int N,M;
	cin>>N>>M;
	
	vector<pair<long long,pair<int,int>>> V;
	
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		long long c;
		cin>>c;
		
		V.emplace_back(c,make_pair(a,b));
	}
	
	vector<vector<pair<int,long long>>> E(N,vector<pair<int,long long>>());
	unionfind uf(N);
	
	sort(V.begin(),V.end());
	long long sum = 0;
	for(int i=0;i<M;i++){
		int a=V[i].second.first,b=V[i].second.second;
		long long cost = V[i].first;
		
		if(uf.unite(a,b)){
			sum+=cost;
			E[a].emplace_back(b,cost);
			E[b].emplace_back(a,cost);
		}
	}
	
	vector<vector<long long>> ans(N,vector<long long>(N,0));
	
	for(int i=0;i<N;i++){
		dfs(ans,E,i,-1,i,0);
	}
	
	int Q;
	cin>>Q;
	
	for(int i=0;i<Q;i++){
		int s,t;
		cin>>s>>t;
		s--;t--;
		
		cout<<sum - ans[s][t]<<endl;
	}
	
		
	
	return 0;
}

### Prompt

Your task is to create a cpp solution 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>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 100000000

struct unionfind{
	vector<int> data;
	vector<int> size;
	unionfind(int n){
		for(int i=0;i<n;i++){
			data.push_back(i);
			size.push_back(1);
		}
	}
	
	int find(int x){
		if(data[x]==x)return x;
		return data[x]=find(data[x]);
	}
	
	bool unite(int x,int y){
		x=find(x);y=find(y);
		if(x==y)return false;
		data[x]=y;
		size[y]+=size[x];
		return true;
	}
	
	bool check(int x,int y){
		return (find(x)==find(y));
	}
	
	int get_size(int x){
		int X = find(x);
		return size[X];
	}
};


void dfs(vector<vector<long long>> &ans,vector<vector<pair<int,long long>>> &E,int now,int parent,int first,long long maxi){
	
	ans[first][now] = maxi;
	
	for(int i=0;i<E[now].size();i++){
		int to = E[now][i].first;
		long long c = E[now][i].second;
		if(to==parent)continue;
		dfs(ans,E,to,now,first,max(maxi,c));
	}
	
}


int main(){
	int N,M;
	cin>>N>>M;
	
	vector<pair<long long,pair<int,int>>> V;
	
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		long long c;
		cin>>c;
		
		V.emplace_back(c,make_pair(a,b));
	}
	
	vector<vector<pair<int,long long>>> E(N,vector<pair<int,long long>>());
	unionfind uf(N);
	
	sort(V.begin(),V.end());
	long long sum = 0;
	for(int i=0;i<M;i++){
		int a=V[i].second.first,b=V[i].second.second;
		long long cost = V[i].first;
		
		if(uf.unite(a,b)){
			sum+=cost;
			E[a].emplace_back(b,cost);
			E[b].emplace_back(a,cost);
		}
	}
	
	vector<vector<long long>> ans(N,vector<long long>(N,0));
	
	for(int i=0;i<N;i++){
		dfs(ans,E,i,-1,i,0);
	}
	
	int Q;
	cin>>Q;
	
	for(int i=0;i<Q;i++){
		int s,t;
		cin>>s>>t;
		s--;t--;
		
		cout<<sum - ans[s][t]<<endl;
	}
	
		
	
	return 0;
}

```