#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=310;
const double EPS=1e-9;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct UnionFind{
    vector<int> par;
    vector<int> dep;
    
    UnionFind(int siz){
        par.assign(siz,0);
        dep.assign(siz,0);
        for(int i=0;i<siz;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(dep[x]<dep[y]){
            par[x]=y;
        }else{
            par[y]=x;
            if(dep[x]==dep[y]){
                dep[x]++;
            }
        }
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
};
struct edge{int from,to;ll cost;};

bool comp(const edge& e1,const edge& e2){
	return e1.cost<e2.cost;
}

struct edge2{int to;ll cost;};
vector<edge2> G[4010];

edge es[400010];
ll s[4010][4010];
void dfs(int now,int p,int st,ll ma){
	for(auto e:G[now]){
		if(e.to==p)continue;
		s[st][e.to]=max(ma,e.cost);
		dfs(e.to,now,st,max(ma,e.cost));
	}
}
	
int main(){
	int n,m,q;cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;a--;b--;
		es[i]={a,b,c};
	}
	sort(es,es+m,comp);
	UnionFind uf(n+1);
	ll ans=0;
	for(int i=0;i<m;i++){
		edge e=es[i];
		if(!uf.same(e.from,e.to)){
			uf.unite(e.from,e.to);
			G[e.from].push_back({e.to,e.cost});
			G[e.to].push_back({e.from,e.cost});
			ans+=e.cost;
		}
	}
	for(int i=0;i<n;i++){
		dfs(i,-1,i,0);
	}
	cin>>q;
	while(q--){
		int a,b;cin>>a>>b;a--;b--;
		cout<<ans-s[a][b]<<endl;
	}
		
    return 0;
}

### Prompt

Develop a solution in Cpp 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>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=310;
const double EPS=1e-9;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct UnionFind{
    vector<int> par;
    vector<int> dep;
    
    UnionFind(int siz){
        par.assign(siz,0);
        dep.assign(siz,0);
        for(int i=0;i<siz;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(dep[x]<dep[y]){
            par[x]=y;
        }else{
            par[y]=x;
            if(dep[x]==dep[y]){
                dep[x]++;
            }
        }
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
};
struct edge{int from,to;ll cost;};

bool comp(const edge& e1,const edge& e2){
	return e1.cost<e2.cost;
}

struct edge2{int to;ll cost;};
vector<edge2> G[4010];

edge es[400010];
ll s[4010][4010];
void dfs(int now,int p,int st,ll ma){
	for(auto e:G[now]){
		if(e.to==p)continue;
		s[st][e.to]=max(ma,e.cost);
		dfs(e.to,now,st,max(ma,e.cost));
	}
}
	
int main(){
	int n,m,q;cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;a--;b--;
		es[i]={a,b,c};
	}
	sort(es,es+m,comp);
	UnionFind uf(n+1);
	ll ans=0;
	for(int i=0;i<m;i++){
		edge e=es[i];
		if(!uf.same(e.from,e.to)){
			uf.unite(e.from,e.to);
			G[e.from].push_back({e.to,e.cost});
			G[e.to].push_back({e.from,e.cost});
			ans+=e.cost;
		}
	}
	for(int i=0;i<n;i++){
		dfs(i,-1,i,0);
	}
	cin>>q;
	while(q--){
		int a,b;cin>>a>>b;a--;b--;
		cout<<ans-s[a][b]<<endl;
	}
		
    return 0;
}

```