#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

struct PartialPersistentUnionFind {
	std::vector<std::vector<std::pair<int, int>>> history;
	std::vector<int> data, time;
	int now = 0;
	
	PartialPersistentUnionFind(int n) {
		history.assign(n, std::vector<std::pair<int, int>>(1, {0, -1}));
		time.assign(n, 1 << 30);
		data.assign(n, -1);
		now = 0;
	}
	
	int unite(int x, int y) {
		x = find(++now, x);
		y = find(now, y);
		if(x == y) return now;
		if(data[x] > data[y]) std::swap(x, y);
		data[x] += data[y];
		data[y] = x;
		history[x].push_back({now, data[x]});
		time[y] = now;
		return now;
	}
	
	int find(int t, int k) {
		if(time[k] > t) return k;
		return find(t, data[k]);
	}
	
	bool same(int t, int x, int y) {
		return find(t, x) == find(t, y);
	}
	
	int size(int t, int x) {
		x = find(t, x);
		return -std::prev(lower_bound(begin(history[x]), end(history[x]), std::make_pair(t, 0)))->second;
	}
};

int main(){
	int n, m; cin >> n >> m;
	std::vector<std::pair<int, std::pair<int, int>>> vec(m);
	for(int i = 0; i < m; i++) cin >> vec[i].second.first >> vec[i].second.second >> vec[i].first;
	sort(begin(vec), end(vec));
	
	int now = 1;
	i64 cost = 0;
	std::vector<int> pos;
	PartialPersistentUnionFind uf(n);
	for(int i = 0; i < m; i++) {
		i64 c = vec[i].first;
		auto p = vec[i].second;
		int x = p.first - 1, y = p.second - 1;
		
		if(uf.same(now, x, y)) continue;
		uf.unite(x, y); ++now;
		pos.push_back(c);
		cost += c;
	}
	
	int q; cin >> q;
	while(q--) {
		int x, y; cin >> x >> y; x--; y--;
		
		int ok = 0, ng = now;
		while(std::abs(ok - ng) > 1) {
			int mid = (ok + ng) / 2, sz = -1;
			
			if(!uf.same(mid, x, y)) ok = mid;
			else ng = mid;
		}
		
		cout << cost - pos[ok] << endl;
	}
	return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

struct PartialPersistentUnionFind {
	std::vector<std::vector<std::pair<int, int>>> history;
	std::vector<int> data, time;
	int now = 0;
	
	PartialPersistentUnionFind(int n) {
		history.assign(n, std::vector<std::pair<int, int>>(1, {0, -1}));
		time.assign(n, 1 << 30);
		data.assign(n, -1);
		now = 0;
	}
	
	int unite(int x, int y) {
		x = find(++now, x);
		y = find(now, y);
		if(x == y) return now;
		if(data[x] > data[y]) std::swap(x, y);
		data[x] += data[y];
		data[y] = x;
		history[x].push_back({now, data[x]});
		time[y] = now;
		return now;
	}
	
	int find(int t, int k) {
		if(time[k] > t) return k;
		return find(t, data[k]);
	}
	
	bool same(int t, int x, int y) {
		return find(t, x) == find(t, y);
	}
	
	int size(int t, int x) {
		x = find(t, x);
		return -std::prev(lower_bound(begin(history[x]), end(history[x]), std::make_pair(t, 0)))->second;
	}
};

int main(){
	int n, m; cin >> n >> m;
	std::vector<std::pair<int, std::pair<int, int>>> vec(m);
	for(int i = 0; i < m; i++) cin >> vec[i].second.first >> vec[i].second.second >> vec[i].first;
	sort(begin(vec), end(vec));
	
	int now = 1;
	i64 cost = 0;
	std::vector<int> pos;
	PartialPersistentUnionFind uf(n);
	for(int i = 0; i < m; i++) {
		i64 c = vec[i].first;
		auto p = vec[i].second;
		int x = p.first - 1, y = p.second - 1;
		
		if(uf.same(now, x, y)) continue;
		uf.unite(x, y); ++now;
		pos.push_back(c);
		cost += c;
	}
	
	int q; cin >> q;
	while(q--) {
		int x, y; cin >> x >> y; x--; y--;
		
		int ok = 0, ng = now;
		while(std::abs(ok - ng) > 1) {
			int mid = (ok + ng) / 2, sz = -1;
			
			if(!uf.same(mid, x, y)) ok = mid;
			else ng = mid;
		}
		
		cout << cost - pos[ok] << endl;
	}
	return 0;
}

```