#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define llint long long

using namespace std;

struct edge{
	llint to, cost;
	edge(llint a, llint b){
		to = a, cost = b;
	}
};

llint parent[4005];
llint N, M, Q;
vector< pair<llint, pair<llint, llint> > > vec;
vector<edge> G[4005];
llint dist[4005][4005];

void init(){
	for(llint i = 1; i <= N; i++){
		parent[i] = i;
	}
}

llint root(llint i){
	if(parent[i] == i) return i;
	return parent[i] = root(parent[i]);
}

bool same(llint i, llint j)
{
	return root(i) == root(j);
}

void unite(llint i, llint j)
{
	llint root_i = root(i), root_j = root(j);
	if(root_i == root_j) return;
	parent[root_i] = root_j;
}

void dfs(llint v, llint prev, llint s, llint val)
{
	dist[s][v] = val;
	for(llint i = 0; i < G[v].size(); i++){
		if(G[v][i].to == prev) continue;
		dfs(G[v][i].to, v, s, max(val, G[v][i].cost));
	}
}

int main(void)
{
	cin >> N >> M;
	llint a, b, c;
	for(llint i = 0; i < M; i++){
		cin >> a >> b >> c;
		vec.push_back( make_pair(c, make_pair(a, b) ) );
	}
	sort(vec.begin(), vec.end());
	
	init();
	llint cost = 0;
	for(llint i = 0; i < vec.size(); i++){
		a = vec[i].second.first, b = vec[i].second.second;
		if(same(a, b)) continue;
		unite(a, b);
		cost += vec[i].first;
		G[a].push_back(edge(b, vec[i].first));
		G[b].push_back(edge(a, vec[i].first));
	}
	
	for(llint i = 1; i <= N; i++){
		dfs(i, -1, i, 0);
	}
	
	cin >> Q;
	llint S, T;
	for(llint q = 0; q < Q; q++){
		cin >> S >> T;
		cout << cost - dist[S][T] << endl;
	}
	return 0;
}
### 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 <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define llint long long

using namespace std;

struct edge{
	llint to, cost;
	edge(llint a, llint b){
		to = a, cost = b;
	}
};

llint parent[4005];
llint N, M, Q;
vector< pair<llint, pair<llint, llint> > > vec;
vector<edge> G[4005];
llint dist[4005][4005];

void init(){
	for(llint i = 1; i <= N; i++){
		parent[i] = i;
	}
}

llint root(llint i){
	if(parent[i] == i) return i;
	return parent[i] = root(parent[i]);
}

bool same(llint i, llint j)
{
	return root(i) == root(j);
}

void unite(llint i, llint j)
{
	llint root_i = root(i), root_j = root(j);
	if(root_i == root_j) return;
	parent[root_i] = root_j;
}

void dfs(llint v, llint prev, llint s, llint val)
{
	dist[s][v] = val;
	for(llint i = 0; i < G[v].size(); i++){
		if(G[v][i].to == prev) continue;
		dfs(G[v][i].to, v, s, max(val, G[v][i].cost));
	}
}

int main(void)
{
	cin >> N >> M;
	llint a, b, c;
	for(llint i = 0; i < M; i++){
		cin >> a >> b >> c;
		vec.push_back( make_pair(c, make_pair(a, b) ) );
	}
	sort(vec.begin(), vec.end());
	
	init();
	llint cost = 0;
	for(llint i = 0; i < vec.size(); i++){
		a = vec[i].second.first, b = vec[i].second.second;
		if(same(a, b)) continue;
		unite(a, b);
		cost += vec[i].first;
		G[a].push_back(edge(b, vec[i].first));
		G[b].push_back(edge(a, vec[i].first));
	}
	
	for(llint i = 1; i <= N; i++){
		dfs(i, -1, i, 0);
	}
	
	cin >> Q;
	llint S, T;
	for(llint q = 0; q < Q; q++){
		cin >> S >> T;
		cout << cost - dist[S][T] << endl;
	}
	return 0;
}
```