            #include <bits/stdc++.h>
            #include<iostream>
            #include<cstdio>
            #include<vector>
            #include<queue>
            #include<map>
            #include<cstring>
            #include<string>
            #include <math.h>
            #include<algorithm>
        //    #include <boost/multiprecision/cpp_int.hpp>
            #include<functional>
          #define int long long
            #define inf  1000000007
            #define pa pair<int,int>
    #define ll long long
            #define pal pair<ll,ll>
            #define ppa pair<int,pa>
            #define  mp make_pair
            #define  pb push_back
            #define EPS (1e-10)
            #define equals(a,b) (fabs((a)-(b))<EPS)
     
            using namespace std;
     
            class Point{
            	public:
            	double x,y;
            	Point(double x=0,double y=0):x(x),y(y) {}
            	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
            	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
            	Point operator * (double a) {return Point(x*a,y*a);}
            	Point operator / (double a) {return Point(x/a,y/a);}
            	double absv() {return sqrt(norm());}
            	double norm() {return x*x+y*y;}
            	bool operator < (const Point &p) const{
            		return x != p.x ? x<p.x: y<p.y;
            	}
            	bool operator == (const Point &p) const{
            		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
            	}
            };
            typedef Point Vector;
     
            struct Segment{
            Point p1,p2;
            };
     
        double hen(Vector a){
        if(fabs(a.x)<EPS && a.y>0) return acos(0);
        else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
        else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
        else if(fabs(a.y)<EPS && a.x>0) return 0.0;
        else if(a.y>0) return acos(a.x/a.absv());
        else return 2*acos(0)+acos(-a.x/a.absv());
     
        }
     
int gcd(int v,int b){
	if(v>b) return gcd(b,v);
	if(v==b) return b;
	if(b%v==0) return v;
	return gcd(v,b%v);
}
            double dot(Vector a,Vector b){
            	return a.x*b.x+a.y*b.y;
            }
            double cross(Vector a,Vector b){
            	return a.x*b.y-a.y*b.x;
            }
        
            //----------------kokomade tenpure------------

int par[100100],ranks[100100];     

void shoki(int n){
	for(int i=0;i<n;i++){
		par[i]=i;
		ranks[i]=0;
	}
}

int root(int x){
	return par[x]==x ? x : par[x]=root(par[x]);
}

bool same(int x,int y){
return root(x)==root(y);
}

void unite(int x,int y){
 x=root(x);
 y=root(y);
 if(x==y) return;
 if(ranks[x]<ranks[y]) par[x]=y;
 else {
	par[y]=x;
	if(ranks[x]==ranks[y]) ranks[x]=ranks[x]+1;
 }
}
int shiten;

vector<ppa> ve;
vector<pa> G[5000];
int omoi[4010][4010];


	void dfs(int ima,int mae,int omosa){
		omoi[shiten][ima]=omosa;
		for(int i=0;i<G[ima].size();i++){
			if(G[ima][i].first==mae) continue;
			dfs(G[ima][i].first,ima,max(omosa,G[ima][i].second));
		}
		return;
	} 

    signed  main(){
    	shoki(100000);
    	int n,m;
    	cin>>n>>m;
    	for(int i=0;i<m;i++){
    		int a,b,c;
    		cin>>a>>b>>c;
    		ve.pb(mp(c,mp(a,b)));
    		
    	}
    	int cnt=0;
    	int cost=0;
    	sort(ve.begin(),ve.end());
    	for(int i=0;i<m;i++){
    		pa zzz=ve[i].second;
    		
    		if(same(zzz.first,zzz.second)) continue;
    	    unite(zzz.first,zzz.second);
    		G[zzz.first].pb(mp(zzz.second,ve[i].first));
    		G[zzz.second].pb(mp(zzz.first,ve[i].first));
    		cost += ve[i].first;
    		cnt++;
    		if(cnt>=n-1) break;
    	}
    	
    	
    	for( shiten=1;shiten<=n;shiten++){
    		dfs(shiten,-1,0);
    	}	
    	
    	
    	int q;
    	cin>>q;
    	for(int i=0;i<q;i++){
    		int s,t;
    		cin>>s>>t;
    		cout<<cost-omoi[s][t]<<endl;
    	}

    //	printf("%.10f\n",ans);
    	return 0;
    }
### Prompt

Please create a solution in CPP 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 <bits/stdc++.h>
            #include<iostream>
            #include<cstdio>
            #include<vector>
            #include<queue>
            #include<map>
            #include<cstring>
            #include<string>
            #include <math.h>
            #include<algorithm>
        //    #include <boost/multiprecision/cpp_int.hpp>
            #include<functional>
          #define int long long
            #define inf  1000000007
            #define pa pair<int,int>
    #define ll long long
            #define pal pair<ll,ll>
            #define ppa pair<int,pa>
            #define  mp make_pair
            #define  pb push_back
            #define EPS (1e-10)
            #define equals(a,b) (fabs((a)-(b))<EPS)
     
            using namespace std;
     
            class Point{
            	public:
            	double x,y;
            	Point(double x=0,double y=0):x(x),y(y) {}
            	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
            	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
            	Point operator * (double a) {return Point(x*a,y*a);}
            	Point operator / (double a) {return Point(x/a,y/a);}
            	double absv() {return sqrt(norm());}
            	double norm() {return x*x+y*y;}
            	bool operator < (const Point &p) const{
            		return x != p.x ? x<p.x: y<p.y;
            	}
            	bool operator == (const Point &p) const{
            		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
            	}
            };
            typedef Point Vector;
     
            struct Segment{
            Point p1,p2;
            };
     
        double hen(Vector a){
        if(fabs(a.x)<EPS && a.y>0) return acos(0);
        else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
        else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
        else if(fabs(a.y)<EPS && a.x>0) return 0.0;
        else if(a.y>0) return acos(a.x/a.absv());
        else return 2*acos(0)+acos(-a.x/a.absv());
     
        }
     
int gcd(int v,int b){
	if(v>b) return gcd(b,v);
	if(v==b) return b;
	if(b%v==0) return v;
	return gcd(v,b%v);
}
            double dot(Vector a,Vector b){
            	return a.x*b.x+a.y*b.y;
            }
            double cross(Vector a,Vector b){
            	return a.x*b.y-a.y*b.x;
            }
        
            //----------------kokomade tenpure------------

int par[100100],ranks[100100];     

void shoki(int n){
	for(int i=0;i<n;i++){
		par[i]=i;
		ranks[i]=0;
	}
}

int root(int x){
	return par[x]==x ? x : par[x]=root(par[x]);
}

bool same(int x,int y){
return root(x)==root(y);
}

void unite(int x,int y){
 x=root(x);
 y=root(y);
 if(x==y) return;
 if(ranks[x]<ranks[y]) par[x]=y;
 else {
	par[y]=x;
	if(ranks[x]==ranks[y]) ranks[x]=ranks[x]+1;
 }
}
int shiten;

vector<ppa> ve;
vector<pa> G[5000];
int omoi[4010][4010];


	void dfs(int ima,int mae,int omosa){
		omoi[shiten][ima]=omosa;
		for(int i=0;i<G[ima].size();i++){
			if(G[ima][i].first==mae) continue;
			dfs(G[ima][i].first,ima,max(omosa,G[ima][i].second));
		}
		return;
	} 

    signed  main(){
    	shoki(100000);
    	int n,m;
    	cin>>n>>m;
    	for(int i=0;i<m;i++){
    		int a,b,c;
    		cin>>a>>b>>c;
    		ve.pb(mp(c,mp(a,b)));
    		
    	}
    	int cnt=0;
    	int cost=0;
    	sort(ve.begin(),ve.end());
    	for(int i=0;i<m;i++){
    		pa zzz=ve[i].second;
    		
    		if(same(zzz.first,zzz.second)) continue;
    	    unite(zzz.first,zzz.second);
    		G[zzz.first].pb(mp(zzz.second,ve[i].first));
    		G[zzz.second].pb(mp(zzz.first,ve[i].first));
    		cost += ve[i].first;
    		cnt++;
    		if(cnt>=n-1) break;
    	}
    	
    	
    	for( shiten=1;shiten<=n;shiten++){
    		dfs(shiten,-1,0);
    	}	
    	
    	
    	int q;
    	cin>>q;
    	for(int i=0;i<q;i++){
    		int s,t;
    		cin>>s>>t;
    		cout<<cost-omoi[s][t]<<endl;
    	}

    //	printf("%.10f\n",ans);
    	return 0;
    }
```