#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;


struct edge
{
	long long from; long long to; long long cost; 
	bool operator<(const edge& rhs) const {
		return cost > rhs.cost;
	}
};

priority_queue<edge> pq;

ll const MAX = 4006;
ll dep[MAX];
ll parent_uf[MAX];
ll rk[MAX];

void init(ll n) {
	for (ll i = 1; i <= n; i++) {
		parent_uf[i] = i;
		rk[i] = 1;
	}
}

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

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

void unite(ll x, ll y) {
	if (!same(x, y)) {
		x = parent_uf[x];
		y = parent_uf[y];
		if (rk[x] < rk[y]) {
			parent_uf[x] = y;
		}
		else {
			parent_uf[y] = x;
			if (rk[x] == rk[y]) {
				rk[x]++;
			}
		}
	}
}

ll n, m, q;
vector<edge> G[MAX];

ll make_tree() {
	ll cnt = n - 1;	
	ll ttl = 0;

	while (cnt > 0) {
		edge cur = pq.top();
		pq.pop();
		ll cf = cur.from; ll ct = cur.to; ll cc = cur.cost;
		if (!same(cf, ct)) {
			unite(cf, ct);
			ttl += cur.cost;
			G[cf].push_back({ cf,ct,cc });
			G[ct].push_back({ ct,cf,cc });
			cnt--;
		}
	}
	return ttl;
}

ll parent[MAX];
ll costing[MAX];

void dfs() {
	parent[1] = 1;
	stack<ll> st;
	st.push(1);
	dep[1] = 0;
	while (!st.empty()) {
		ll cur = st.top();
		st.pop();
		for (ll i = 0; i < SIZE(G[cur]); i++) {
			
			ll next = G[cur][i].to;
			if (next == parent[cur]) {
				continue;
			}
			//cout << cur << " " << next << endl;
			parent[next] = cur;
			dep[next] = dep[cur] + 1;
			costing[next] = G[cur][i].cost;
			//cout << costing[next] << endl;
			st.push(next);
		}
	}
}

ll dp[MAX][MAX] = {};

ll query(ll s, ll t) {
	if (s == t) {
		return 0;
	}	
	if (dep[s] < dep[t]) {
		swap(s, t);
	}

	if (dp[s][t] != 0) {
		return dp[s][t];
	}
	//cout << v << " ?" << endl;
	dp[s][t] = max(costing[s],query(parent[s], t));
	return dp[s][t];
}

int main() {
	cin >> n >> m;
	init(n);
	REP(i, 1, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		pq.push({ a,b,c });
	}
	ll ttl = make_tree();
	dfs();
	cin >> q;
	REP(i, 1, q) {
		ll s, t;
		cin >> s >> t;
		cout << ttl - query(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<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;


struct edge
{
	long long from; long long to; long long cost; 
	bool operator<(const edge& rhs) const {
		return cost > rhs.cost;
	}
};

priority_queue<edge> pq;

ll const MAX = 4006;
ll dep[MAX];
ll parent_uf[MAX];
ll rk[MAX];

void init(ll n) {
	for (ll i = 1; i <= n; i++) {
		parent_uf[i] = i;
		rk[i] = 1;
	}
}

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

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

void unite(ll x, ll y) {
	if (!same(x, y)) {
		x = parent_uf[x];
		y = parent_uf[y];
		if (rk[x] < rk[y]) {
			parent_uf[x] = y;
		}
		else {
			parent_uf[y] = x;
			if (rk[x] == rk[y]) {
				rk[x]++;
			}
		}
	}
}

ll n, m, q;
vector<edge> G[MAX];

ll make_tree() {
	ll cnt = n - 1;	
	ll ttl = 0;

	while (cnt > 0) {
		edge cur = pq.top();
		pq.pop();
		ll cf = cur.from; ll ct = cur.to; ll cc = cur.cost;
		if (!same(cf, ct)) {
			unite(cf, ct);
			ttl += cur.cost;
			G[cf].push_back({ cf,ct,cc });
			G[ct].push_back({ ct,cf,cc });
			cnt--;
		}
	}
	return ttl;
}

ll parent[MAX];
ll costing[MAX];

void dfs() {
	parent[1] = 1;
	stack<ll> st;
	st.push(1);
	dep[1] = 0;
	while (!st.empty()) {
		ll cur = st.top();
		st.pop();
		for (ll i = 0; i < SIZE(G[cur]); i++) {
			
			ll next = G[cur][i].to;
			if (next == parent[cur]) {
				continue;
			}
			//cout << cur << " " << next << endl;
			parent[next] = cur;
			dep[next] = dep[cur] + 1;
			costing[next] = G[cur][i].cost;
			//cout << costing[next] << endl;
			st.push(next);
		}
	}
}

ll dp[MAX][MAX] = {};

ll query(ll s, ll t) {
	if (s == t) {
		return 0;
	}	
	if (dep[s] < dep[t]) {
		swap(s, t);
	}

	if (dp[s][t] != 0) {
		return dp[s][t];
	}
	//cout << v << " ?" << endl;
	dp[s][t] = max(costing[s],query(parent[s], t));
	return dp[s][t];
}

int main() {
	cin >> n >> m;
	init(n);
	REP(i, 1, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		pq.push({ a,b,c });
	}
	ll ttl = make_tree();
	dfs();
	cin >> q;
	REP(i, 1, q) {
		ll s, t;
		cin >> s >> t;
		cout << ttl - query(s, t) << endl;
	}
}
```