#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define F first
#define S second

const int MAXN = 4e5 + 10;

int n, m, from[MAXN], to[MAXN], w[MAXN], sec[MAXN], q;
int par[MAXN], ss[4010][4010];
ll sm;
vector<pair<int, int>>	adj[MAXN];
bool vis[4010];

bool cmp(int u, int v){return w[u] < w[v];}

int getPar(int v){return par[v]==v?v:par[v]=getPar(par[v]);}

void dfs(int v, int p, int z = -1){
	ss[p][v] = z;
	vis[v] = 1;
	for (auto e:adj[v])
		if (!vis[e.F])
			dfs(e.F, p, max(z, e.S));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> from[i] >> to[i] >> w[i], from[i]--, to[i]--;
	iota(sec, sec + m, 0);
	sort(sec, sec + m, cmp);
	iota(par, par + n, 0);
	for (int i = 0; i < m; i++){
		int e = sec[i];
		int u = from[e], v = to[e];
		int pu = getPar(u), pv = getPar(v);
		if (pu == pv)	continue;
		adj[u].push_back({v, w[e]});
		adj[v].push_back({u, w[e]});
		par[pu] = pv;
		sm += w[e];
	}
	for (int i = 0; i < n; i++){
		memset(vis, 0, sizeof(vis));
		dfs(i, i);
	}
	cin >> q;
	while (q--){
		int u, v;	cin >> u >> v, u--, v--;
		printf("%lld\n", sm - ss[u][v]);
	}
	return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;

#define F first
#define S second

const int MAXN = 4e5 + 10;

int n, m, from[MAXN], to[MAXN], w[MAXN], sec[MAXN], q;
int par[MAXN], ss[4010][4010];
ll sm;
vector<pair<int, int>>	adj[MAXN];
bool vis[4010];

bool cmp(int u, int v){return w[u] < w[v];}

int getPar(int v){return par[v]==v?v:par[v]=getPar(par[v]);}

void dfs(int v, int p, int z = -1){
	ss[p][v] = z;
	vis[v] = 1;
	for (auto e:adj[v])
		if (!vis[e.F])
			dfs(e.F, p, max(z, e.S));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> from[i] >> to[i] >> w[i], from[i]--, to[i]--;
	iota(sec, sec + m, 0);
	sort(sec, sec + m, cmp);
	iota(par, par + n, 0);
	for (int i = 0; i < m; i++){
		int e = sec[i];
		int u = from[e], v = to[e];
		int pu = getPar(u), pv = getPar(v);
		if (pu == pv)	continue;
		adj[u].push_back({v, w[e]});
		adj[v].push_back({u, w[e]});
		par[pu] = pv;
		sm += w[e];
	}
	for (int i = 0; i < n; i++){
		memset(vis, 0, sizeof(vis));
		dfs(i, i);
	}
	cin >> q;
	while (q--){
		int u, v;	cin >> u >> v, u--, v--;
		printf("%lld\n", sm - ss[u][v]);
	}
	return 0;
}

```