#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<int,pii> edge;

const int N = 4005;
int uf[N];

int id(int v) {
	if(uf[v] == v) return v;
	return uf[v] = id(uf[v]);
}

void merge(int u, int v) {
	uf[id(u)] = id(v);
}

vector<edge> v;

vvi T;
vvi W;
int d[4005][4005],n,m,q;

void find(int f, int s, int t, int ds) {
	d[s][t] = ds;
	for(int i = 0; i < T[t].size(); ++i) {
		int v = T[t][i];
		if(v == f) continue;
		find(t,s,v,max(W[t][i],ds));
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie();
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
		uf[i] = i;
	for(int i = 0;i < m; ++i) {
		int a,b,c;
		cin >> a >> b >> c;
		v.push_back(edge(c,pii(a-1,b-1)));
	}
	sort(v.begin(),v.end());
	ll wt = 0;
	T = vvi(n,vi());
	W = vvi(n,vi());
	for(int i = 0; i < v.size(); ++i) {
		int a = v[i].second.first,b=v[i].second.second;
		if(id(a) == id(b))
			continue;
		merge(a,b);
		wt += v[i].first;
		T[a].push_back(b);
		T[b].push_back(a);
		W[a].push_back(v[i].first);
		W[b].push_back(v[i].first);
	}
	for(int i = 0; i < n; ++i)
		find(-1,i,i,0);
	cin >> q;
	while(q--) {
		int s,t;
		cin >> s >> t;
		--s; --t;
		cout << wt - d[s][t] << "\n";
	}

	return 0;
}
### Prompt

Please formulate 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 <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<int,pii> edge;

const int N = 4005;
int uf[N];

int id(int v) {
	if(uf[v] == v) return v;
	return uf[v] = id(uf[v]);
}

void merge(int u, int v) {
	uf[id(u)] = id(v);
}

vector<edge> v;

vvi T;
vvi W;
int d[4005][4005],n,m,q;

void find(int f, int s, int t, int ds) {
	d[s][t] = ds;
	for(int i = 0; i < T[t].size(); ++i) {
		int v = T[t][i];
		if(v == f) continue;
		find(t,s,v,max(W[t][i],ds));
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie();
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
		uf[i] = i;
	for(int i = 0;i < m; ++i) {
		int a,b,c;
		cin >> a >> b >> c;
		v.push_back(edge(c,pii(a-1,b-1)));
	}
	sort(v.begin(),v.end());
	ll wt = 0;
	T = vvi(n,vi());
	W = vvi(n,vi());
	for(int i = 0; i < v.size(); ++i) {
		int a = v[i].second.first,b=v[i].second.second;
		if(id(a) == id(b))
			continue;
		merge(a,b);
		wt += v[i].first;
		T[a].push_back(b);
		T[b].push_back(a);
		W[a].push_back(v[i].first);
		W[b].push_back(v[i].first);
	}
	for(int i = 0; i < n; ++i)
		find(-1,i,i,0);
	cin >> q;
	while(q--) {
		int s,t;
		cin >> s >> t;
		--s; --t;
		cout << wt - d[s][t] << "\n";
	}

	return 0;
}
```