#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_V 5000
#define ll long long
using namespace std;

ll par[MAX_V],ran[MAX_V];
void init(int n){
	for(int i=0;i<n;i++){
		par[i] = i;
		ran[i] = i;
	}
}

ll find(ll x){
	if(par[x]==x){
		return x;
	}else{
		return par[x] = find(par[x]);
	}
}

void unite(ll x, ll y){
	x = find(x);
	y = find(y);
	if(x==y) return;
	if(ran[x]<ran[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(ran[x]==ran[y]) ran[x]++;
	}
}

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

struct edge{ll u,v,cost;};
ll n,m;
vector<edge> E;
vector<edge> G[MAX_V];

bool comp(const edge& e1, const edge& e2){
	return e1.cost<e2.cost;
}

ll kruscal(){
	sort(E.begin(),E.end(),comp);
	init(n);
	long long res = 0;
	for(int i=0;i<E.size();i++){
		edge e = E[i];
		if(!same(e.u,e.v)){
			unite(e.u,e.v);
			res += e.cost;
			G[e.u].push_back({e.u,e.v,e.cost});
			G[e.v].push_back({e.v,e.u,e.cost});
		}
	}
	return res;
}

bool used[MAX_V];
ll d[MAX_V];
ll x[MAX_V][MAX_V];
void dfs(int s){
	used[s] = true;
	for(int i=0;i<G[s].size();i++){
		edge e = G[s][i];
		if(!used[e.v]){
			d[e.v] = max(d[s],e.cost);
			dfs(e.v);
		}
	}
}

int main(){
	int i,j;
	cin >> n >> m;
	for(i=0;i<m;i++){
		ll a,b,c;
		cin >> a >> b >> c;
		a--; b--;
		edge e;
		e.u = a; e.v = b; e.cost = c;
		E.push_back(e);
	}
	
	ll res = kruscal();
	
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			used[j] = false;
			d[j] = 0;
		}
		dfs(i);
		for(j=0;j<n;j++){
			x[i][j] = d[j];
		}
	}
	int q;
	cin >> q;
	for(i=0;i<q;i++){
		int s,t;
		cin >> s >> t;
		s--; t--;
		cout << res - x[s][t] << endl;
	}
}

### Prompt

Your challenge is to write 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>

#define MAX_V 5000
#define ll long long
using namespace std;

ll par[MAX_V],ran[MAX_V];
void init(int n){
	for(int i=0;i<n;i++){
		par[i] = i;
		ran[i] = i;
	}
}

ll find(ll x){
	if(par[x]==x){
		return x;
	}else{
		return par[x] = find(par[x]);
	}
}

void unite(ll x, ll y){
	x = find(x);
	y = find(y);
	if(x==y) return;
	if(ran[x]<ran[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(ran[x]==ran[y]) ran[x]++;
	}
}

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

struct edge{ll u,v,cost;};
ll n,m;
vector<edge> E;
vector<edge> G[MAX_V];

bool comp(const edge& e1, const edge& e2){
	return e1.cost<e2.cost;
}

ll kruscal(){
	sort(E.begin(),E.end(),comp);
	init(n);
	long long res = 0;
	for(int i=0;i<E.size();i++){
		edge e = E[i];
		if(!same(e.u,e.v)){
			unite(e.u,e.v);
			res += e.cost;
			G[e.u].push_back({e.u,e.v,e.cost});
			G[e.v].push_back({e.v,e.u,e.cost});
		}
	}
	return res;
}

bool used[MAX_V];
ll d[MAX_V];
ll x[MAX_V][MAX_V];
void dfs(int s){
	used[s] = true;
	for(int i=0;i<G[s].size();i++){
		edge e = G[s][i];
		if(!used[e.v]){
			d[e.v] = max(d[s],e.cost);
			dfs(e.v);
		}
	}
}

int main(){
	int i,j;
	cin >> n >> m;
	for(i=0;i<m;i++){
		ll a,b,c;
		cin >> a >> b >> c;
		a--; b--;
		edge e;
		e.u = a; e.v = b; e.cost = c;
		E.push_back(e);
	}
	
	ll res = kruscal();
	
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			used[j] = false;
			d[j] = 0;
		}
		dfs(i);
		for(j=0;j<n;j++){
			x[i][j] = d[j];
		}
	}
	int q;
	cin >> q;
	for(i=0;i<q;i++){
		int s,t;
		cin >> s >> t;
		s--; t--;
		cout << res - x[s][t] << endl;
	}
}

```