#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, P> Pll;
typedef pair<int, ll> Pl;

int par[4002];
int rk[4002];
 
void init(int n){
	for(int i=0; i<n; i++){
		par[i]=i;
	}
}
 
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}
 
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
	}
}
 
bool same(int x, int y){
	return find(x)==find(y);
}

vector<Pl> g[4000];
ll mx[4000][4000];
bool used[4000];

void dfs(int s, int x){
	used[x]=1;
	for(int i=0; i<g[x].size(); i++){
		int y=g[x][i].first;
		if(used[y]) continue;
		mx[s][y]=max(mx[s][x], g[x][i].second);
		dfs(s, y);
	}
}

int main()
{
	int n, m;
	cin>>n>>m;
	vector<Pll> eg;
	for(int i=0; i<m; i++){
		int a, b; ll c;
		cin>>a>>b>>c;
		a--; b--;
		eg.push_back(Pll(c, P(a, b)));
	}
	sort(eg.begin(), eg.end());
	init(n);
	ll sum=0;
	int ct=0;
	for(int i=0; i<m; i++){
		int a=eg[i].second.first, b=eg[i].second.second;
		if(same(a, b)) continue;
		unite(a, b);
		ct++;
		ll c=eg[i].first;
		sum+=c;
		g[a].push_back(Pl(b, c));
		g[b].push_back(Pl(a, c));
		if(ct==n-1) break;
	}
	for(int i=0; i<n; i++){
		fill(used, used+n, 0);
		dfs(i, i);
	}
	int q;
	cin>>q;
	for(int i=0; i<q; i++){
		int s, t;
		cin>>s>>t;
		s--; t--;
		cout<<sum-mx[s][t]<<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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, P> Pll;
typedef pair<int, ll> Pl;

int par[4002];
int rk[4002];
 
void init(int n){
	for(int i=0; i<n; i++){
		par[i]=i;
	}
}
 
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}
 
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
	}
}
 
bool same(int x, int y){
	return find(x)==find(y);
}

vector<Pl> g[4000];
ll mx[4000][4000];
bool used[4000];

void dfs(int s, int x){
	used[x]=1;
	for(int i=0; i<g[x].size(); i++){
		int y=g[x][i].first;
		if(used[y]) continue;
		mx[s][y]=max(mx[s][x], g[x][i].second);
		dfs(s, y);
	}
}

int main()
{
	int n, m;
	cin>>n>>m;
	vector<Pll> eg;
	for(int i=0; i<m; i++){
		int a, b; ll c;
		cin>>a>>b>>c;
		a--; b--;
		eg.push_back(Pll(c, P(a, b)));
	}
	sort(eg.begin(), eg.end());
	init(n);
	ll sum=0;
	int ct=0;
	for(int i=0; i<m; i++){
		int a=eg[i].second.first, b=eg[i].second.second;
		if(same(a, b)) continue;
		unite(a, b);
		ct++;
		ll c=eg[i].first;
		sum+=c;
		g[a].push_back(Pl(b, c));
		g[b].push_back(Pl(a, c));
		if(ct==n-1) break;
	}
	for(int i=0; i<n; i++){
		fill(used, used+n, 0);
		dfs(i, i);
	}
	int q;
	cin>>q;
	for(int i=0; i<q; i++){
		int s, t;
		cin>>s>>t;
		s--; t--;
		cout<<sum-mx[s][t]<<endl;
	}
    return 0;
}
```