#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 1000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
struct UnionFind{
	int par[4010],rank[4010];
	void init(){
		for(int i=0;i<4010;i++){
			par[i]=i;
			rank[i]=0;
		}
	}
	int find(int x){
		if(par[x]==x)return x;
		else return par[x]=find(par[x]);
	}
	void unite(int x,int y){
		x = find(x);
		y = find(y);
		if(x==y)return;
		if(rank[x]>rank[y])par[y]=x;
		else{
			par[x]=y;
			rank[y]++;
		}
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
}uf;
struct edge{
	int from,to;
	ll cost;
	edge(){}
	edge(int from,int to,ll cost):from(from),to(to),cost(cost){}
	bool operator < (const edge &a) const{
		return cost < a.cost;
	}
};
int N,M,Q;
vector<edge> es;
vector<edge> g[4010];
int par[15][4010];
ll cost[15][4010];
int depth[4010];
void add_edge(edge e){
	g[e.from].pb(e);
	swap(e.from,e.to);
	g[e.from].pb(e);
}
void dfs(int v,int p,int c,int d){
	depth[v]=d;
	par[0][v]=p;
	cost[0][v]=c;
	for(int i=0;i<g[v].size();i++){
		edge e = g[v][i];
		if(e.to==p)continue;
		dfs(e.to,v,e.cost,d+1);
	}
}
ll query(int u,int v){
	//cout << u << ' ' << v << endl;
	if(depth[u]>depth[v])swap(u,v);
	ll res = 0ll;
	for(int i=14;i>=0;i--){
		if(((depth[v]-depth[u])>>i)&1){
			res = max(res,cost[i][v]);
			v = par[i][v];
		}
	}
	if(u==v)return res;
	for(int i=14;i>=0;i--){
		if(par[i][u]!=par[i][v]){
			res = max(res,cost[i][u]);
			res = max(res,cost[i][v]);
			u = par[i][u];
			v = par[i][v];
		}
	}
	res = max(res,cost[0][u]);
	res = max(res,cost[0][v]);
	assert(par[0][u]==par[0][v]);
	return res;
}
int main(){
	cin >> N >> M;
	for(int i=0;i<M;i++){
		int a,b;
		ll c;
		cin >> a >> b >> c;
		a--;b--;
		es.pb(edge(a,b,c));
	}
	sort(all(es));
	uf.init();
	ll base = 0ll;
	for(int i=0;i<es.size();i++){
		if(uf.same(es[i].from,es[i].to))continue;
		base += es[i].cost;
		uf.unite(es[i].from,es[i].to);
		//cout << es[i].from << ' ' << es[i].to << ' ' << es[i].cost << endl;
		add_edge(es[i]);
	}
	dfs(0,-1,-1,0);
	/*for(int i=0;i<N;i++){
		printf("%d %d %lld\n",i,par[0][i],cost[0][i]);
	}*/
	for(int i=0;i<14;i++){
		for(int j=0;j<N;j++){
			if(par[i][j]==-1){
				par[i+1][j]=-1;
				cost[i+1][j]=cost[i][j];
			}else{
				par[i+1][j]=par[i][par[i][j]];
				cost[i+1][j]=max(cost[i][j],cost[i][par[i][j]]);
			}
		}
	}
	cin >> Q;
	for(int i=0;i<Q;i++){
		int S,T;
		cin >> S >> T;
		S--;T--;
		cout << base-query(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;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 1000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
struct UnionFind{
	int par[4010],rank[4010];
	void init(){
		for(int i=0;i<4010;i++){
			par[i]=i;
			rank[i]=0;
		}
	}
	int find(int x){
		if(par[x]==x)return x;
		else return par[x]=find(par[x]);
	}
	void unite(int x,int y){
		x = find(x);
		y = find(y);
		if(x==y)return;
		if(rank[x]>rank[y])par[y]=x;
		else{
			par[x]=y;
			rank[y]++;
		}
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
}uf;
struct edge{
	int from,to;
	ll cost;
	edge(){}
	edge(int from,int to,ll cost):from(from),to(to),cost(cost){}
	bool operator < (const edge &a) const{
		return cost < a.cost;
	}
};
int N,M,Q;
vector<edge> es;
vector<edge> g[4010];
int par[15][4010];
ll cost[15][4010];
int depth[4010];
void add_edge(edge e){
	g[e.from].pb(e);
	swap(e.from,e.to);
	g[e.from].pb(e);
}
void dfs(int v,int p,int c,int d){
	depth[v]=d;
	par[0][v]=p;
	cost[0][v]=c;
	for(int i=0;i<g[v].size();i++){
		edge e = g[v][i];
		if(e.to==p)continue;
		dfs(e.to,v,e.cost,d+1);
	}
}
ll query(int u,int v){
	//cout << u << ' ' << v << endl;
	if(depth[u]>depth[v])swap(u,v);
	ll res = 0ll;
	for(int i=14;i>=0;i--){
		if(((depth[v]-depth[u])>>i)&1){
			res = max(res,cost[i][v]);
			v = par[i][v];
		}
	}
	if(u==v)return res;
	for(int i=14;i>=0;i--){
		if(par[i][u]!=par[i][v]){
			res = max(res,cost[i][u]);
			res = max(res,cost[i][v]);
			u = par[i][u];
			v = par[i][v];
		}
	}
	res = max(res,cost[0][u]);
	res = max(res,cost[0][v]);
	assert(par[0][u]==par[0][v]);
	return res;
}
int main(){
	cin >> N >> M;
	for(int i=0;i<M;i++){
		int a,b;
		ll c;
		cin >> a >> b >> c;
		a--;b--;
		es.pb(edge(a,b,c));
	}
	sort(all(es));
	uf.init();
	ll base = 0ll;
	for(int i=0;i<es.size();i++){
		if(uf.same(es[i].from,es[i].to))continue;
		base += es[i].cost;
		uf.unite(es[i].from,es[i].to);
		//cout << es[i].from << ' ' << es[i].to << ' ' << es[i].cost << endl;
		add_edge(es[i]);
	}
	dfs(0,-1,-1,0);
	/*for(int i=0;i<N;i++){
		printf("%d %d %lld\n",i,par[0][i],cost[0][i]);
	}*/
	for(int i=0;i<14;i++){
		for(int j=0;j<N;j++){
			if(par[i][j]==-1){
				par[i+1][j]=-1;
				cost[i+1][j]=cost[i][j];
			}else{
				par[i+1][j]=par[i][par[i][j]];
				cost[i+1][j]=max(cost[i][j],cost[i][par[i][j]]);
			}
		}
	}
	cin >> Q;
	for(int i=0;i<Q;i++){
		int S,T;
		cin >> S >> T;
		S--;T--;
		cout << base-query(S,T) << endl;
	}
	return 0;
}
```