#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;

vector<int> par,rk;

void init(const int n){
	par.resize(n);
	rk.resize(n);
	for(int i=0;i<n;++i) par[i]=i;
	fill(rk.begin(),rk.end(),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;
	}else if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]){
			++rk[x];
		}
	}
}

bool same(int x,int y){
	return find(x)==find(y);
}

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

bool cmp(edge e,edge f){
	return e.cost<f.cost;
}

#define MAX_Q 100000

vector<edge> es;

#define MAX_N 4000

vector<int> g[MAX_N];
ll d[MAX_N][MAX_N];

void dfs(int v0,int v){
	for(int j=0;j<g[v].size();++j){
		int e=g[v][j],w=es[e].from;
		if(v==w) w=es[e].to;
		if(d[v0][w]>=0) continue;
		d[v0][w]=max(d[v0][v],es[e].cost);
		dfs(v0,w);
	}
}

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	while(m-->0){
		int a,b,c;
		cin>>a>>b>>c;
		es.pb((edge){--a,--b,c});
	}
	sort(es.begin(),es.end(),cmp);
	init(n);
	ll sc=0;
	for(int j=0,e=0;e<n-1;++j){
		int v=es[j].from,w=es[j].to;
		if(same(v,w)) continue;
		unite(v,w);
		sc+=es[j].cost;
		g[v].pb(j);
		g[w].pb(j);
		++e;
	}
	for(int v=0;v<n;++v){
		fill(d[v],d[v]+n,-1);
		d[v][v]=0;
		dfs(v,v);
	}
	int q;
	scanf("%d",&q);
	while(q-->0){
		int s,t;
		scanf("%d%d",&s,&t);
		printf("%lld\n",sc-d[--s][--t]);
	}
}
### Prompt

In CPP, your task is to solve 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 pb push_back
typedef long long ll;

vector<int> par,rk;

void init(const int n){
	par.resize(n);
	rk.resize(n);
	for(int i=0;i<n;++i) par[i]=i;
	fill(rk.begin(),rk.end(),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;
	}else if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]){
			++rk[x];
		}
	}
}

bool same(int x,int y){
	return find(x)==find(y);
}

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

bool cmp(edge e,edge f){
	return e.cost<f.cost;
}

#define MAX_Q 100000

vector<edge> es;

#define MAX_N 4000

vector<int> g[MAX_N];
ll d[MAX_N][MAX_N];

void dfs(int v0,int v){
	for(int j=0;j<g[v].size();++j){
		int e=g[v][j],w=es[e].from;
		if(v==w) w=es[e].to;
		if(d[v0][w]>=0) continue;
		d[v0][w]=max(d[v0][v],es[e].cost);
		dfs(v0,w);
	}
}

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	while(m-->0){
		int a,b,c;
		cin>>a>>b>>c;
		es.pb((edge){--a,--b,c});
	}
	sort(es.begin(),es.end(),cmp);
	init(n);
	ll sc=0;
	for(int j=0,e=0;e<n-1;++j){
		int v=es[j].from,w=es[j].to;
		if(same(v,w)) continue;
		unite(v,w);
		sc+=es[j].cost;
		g[v].pb(j);
		g[w].pb(j);
		++e;
	}
	for(int v=0;v<n;++v){
		fill(d[v],d[v]+n,-1);
		d[v][v]=0;
		dfs(v,v);
	}
	int q;
	scanf("%d",&q);
	while(q-->0){
		int s,t;
		scanf("%d%d",&s,&t);
		printf("%lld\n",sc-d[--s][--t]);
	}
}
```