#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#include<vector>
struct UF{
	int n;
	vector<int>parent,rank;
	UF(int n_=0):n(n_),parent(n_),rank(n_,1)
	{
		for(int i=0;i<n_;i++)parent[i]=i;
	}
	int find(int a)
	{
		return parent[a]!=a?parent[a]=find(parent[a]):a;
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
	bool unite(int a,int b)
	{
		a=find(a),b=find(b);
		if(a==b)return false;
		if(rank[a]<rank[b])
		{
			parent[a]=b;
			rank[b]+=rank[a];
		}
		else
		{
			parent[b]=a;
			rank[a]+=rank[b];
		}
		return true;
	}
};
int N,M,Q;
vector<pair<int,pair<int,int> > >E;
vector<pair<int,int> >G[4000];
int T[4000][4000];
void dfs(int u,int p,int now,int f)
{
	T[f][u]=now;
	for(pair<int,int>q:G[u])
	{
		if(q.first==p)continue;
		dfs(q.first,u,max(now,q.second),f);
	}
}
int main()
{
	cin>>N>>M;
	for(int i=0;i<M;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		a--,b--;
		E.push_back(make_pair(c,make_pair(a,b)));
	}
	sort(E.begin(),E.end());
	UF uf(N);
	long sum=0;
	for(pair<int,pair<int,int> >p:E)
	{
		int u=p.second.first,v=p.second.second;
		if(uf.unite(u,v))
		{
			sum+=p.first;
			G[u].push_back(make_pair(v,p.first));
			G[v].push_back(make_pair(u,p.first));
		}
	}
	for(int i=0;i<N;i++)
	{
		dfs(i,-1,0,i);
	}
	cin>>Q;
	for(int i=0;i<Q;i++)
	{
		int a,b;cin>>a>>b;
		a--,b--;
		cout<<sum-T[a][b]<<endl;
	}
}
### 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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#include<vector>
struct UF{
	int n;
	vector<int>parent,rank;
	UF(int n_=0):n(n_),parent(n_),rank(n_,1)
	{
		for(int i=0;i<n_;i++)parent[i]=i;
	}
	int find(int a)
	{
		return parent[a]!=a?parent[a]=find(parent[a]):a;
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
	bool unite(int a,int b)
	{
		a=find(a),b=find(b);
		if(a==b)return false;
		if(rank[a]<rank[b])
		{
			parent[a]=b;
			rank[b]+=rank[a];
		}
		else
		{
			parent[b]=a;
			rank[a]+=rank[b];
		}
		return true;
	}
};
int N,M,Q;
vector<pair<int,pair<int,int> > >E;
vector<pair<int,int> >G[4000];
int T[4000][4000];
void dfs(int u,int p,int now,int f)
{
	T[f][u]=now;
	for(pair<int,int>q:G[u])
	{
		if(q.first==p)continue;
		dfs(q.first,u,max(now,q.second),f);
	}
}
int main()
{
	cin>>N>>M;
	for(int i=0;i<M;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		a--,b--;
		E.push_back(make_pair(c,make_pair(a,b)));
	}
	sort(E.begin(),E.end());
	UF uf(N);
	long sum=0;
	for(pair<int,pair<int,int> >p:E)
	{
		int u=p.second.first,v=p.second.second;
		if(uf.unite(u,v))
		{
			sum+=p.first;
			G[u].push_back(make_pair(v,p.first));
			G[v].push_back(make_pair(u,p.first));
		}
	}
	for(int i=0;i<N;i++)
	{
		dfs(i,-1,0,i);
	}
	cin>>Q;
	for(int i=0;i<Q;i++)
	{
		int a,b;cin>>a>>b;
		a--,b--;
		cout<<sum-T[a][b]<<endl;
	}
}
```