#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int N,M,Q,S[400010],T[400010];
ll sum = 0,dist[4001][4001],C[400010];
vector<vector<int>> mst(4010);
int visited[4010] = {0};

int p[4010] = {0},r[4010] = {0};
void init(int N){
	for(int i=0;i<=N;++i) p[i] = i;
}

int root(int a){
	if(p[a] == a) return a;
	return (p[a] = root(p[a]));
}

bool is_same_set(int a,int b){
	return root(a) == root(b);
}

void unite(int a, int b){
	a = root(a);
	b = root(b);
	if(a==b) return;
	if(r[a]<r[b]){
		p[a] = b;
	}else{
		p[b] = a;
		if(r[a] == r[b]) r[a]++;
	}
}

void dfs(int s,int n,ll cost){
	visited[n] = 1;
	for(int i=0;i<mst[n].size();i++){
		int t = mst[n][i];
		if(visited[t]==0){
			ll ma = max(cost,dist[n][t]);
			dist[s][t] = ma;
			dist[t][s] = ma;
			dfs(s,t,ma);
		}
	}
}

int main(){
	cin >> N >> M;
	init(N);
	vector<pair<ll,int>> v;
	for(int i=0;i<M;i++){
		cin >> S[i] >> T[i] >> C[i];
		dist[S[i]][T[i]] = C[i];
		dist[T[i]][S[i]] = C[i];
		v.push_back({C[i],i});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		int t = v[i].second;
		if(!is_same_set(S[t],T[t])){
			sum += C[t];
			unite(S[t],T[t]);
			mst[S[t]].push_back(T[t]);
			mst[T[t]].push_back(S[t]);
		}
	}
	for(int i=1;i<=N;i++){
		dfs(i,i,0);
		for(int j=1;j<=N;j++) visited[j] = 0;
	}
	cin >> Q;
	int a,b;
	for(int i=0;i<Q;i++){
		cin >> a >> b;
		cout << sum-dist[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;
typedef long long ll;
int N,M,Q,S[400010],T[400010];
ll sum = 0,dist[4001][4001],C[400010];
vector<vector<int>> mst(4010);
int visited[4010] = {0};

int p[4010] = {0},r[4010] = {0};
void init(int N){
	for(int i=0;i<=N;++i) p[i] = i;
}

int root(int a){
	if(p[a] == a) return a;
	return (p[a] = root(p[a]));
}

bool is_same_set(int a,int b){
	return root(a) == root(b);
}

void unite(int a, int b){
	a = root(a);
	b = root(b);
	if(a==b) return;
	if(r[a]<r[b]){
		p[a] = b;
	}else{
		p[b] = a;
		if(r[a] == r[b]) r[a]++;
	}
}

void dfs(int s,int n,ll cost){
	visited[n] = 1;
	for(int i=0;i<mst[n].size();i++){
		int t = mst[n][i];
		if(visited[t]==0){
			ll ma = max(cost,dist[n][t]);
			dist[s][t] = ma;
			dist[t][s] = ma;
			dfs(s,t,ma);
		}
	}
}

int main(){
	cin >> N >> M;
	init(N);
	vector<pair<ll,int>> v;
	for(int i=0;i<M;i++){
		cin >> S[i] >> T[i] >> C[i];
		dist[S[i]][T[i]] = C[i];
		dist[T[i]][S[i]] = C[i];
		v.push_back({C[i],i});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		int t = v[i].second;
		if(!is_same_set(S[t],T[t])){
			sum += C[t];
			unite(S[t],T[t]);
			mst[S[t]].push_back(T[t]);
			mst[T[t]].push_back(S[t]);
		}
	}
	for(int i=1;i<=N;i++){
		dfs(i,i,0);
		for(int j=1;j<=N;j++) visited[j] = 0;
	}
	cin >> Q;
	int a,b;
	for(int i=0;i<Q;i++){
		cin >> a >> b;
		cout << sum-dist[a][b] << endl;
	}
}
```