#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const ll inf=1e17;
struct UnionFind{
    vector<ll> data;
    UnionFind(ll size) : data(size, -1) {}
    bool unionSet(ll x,ll y){
        x=root(x);y=root(y);
        if(x==y)return 0;
        if(data[y]<data[x])swap(x,y);
        data[x]+=data[y],data[y]=x;
        return 1;
    }
    bool findSet(ll x,ll y){
        return root(x)==root(y);
    }
    ll root(ll x){
        return data[x]<0 ? x : data[x]=root(data[x]);
    }
    ll size(ll x){
        return -data[root(x)];
    }
};
class KRK{//c++11
	public:
	struct edge{
		ll from,to,cost;
	};
	vector<edge>G;
	vvp tG;
	vvi dp;
	vi used;
	ll n;
	KRK(ll size){
		n=size;
	}
	void add_edge(ll a,ll b,ll c){
		edge e={a,b,c};
		G.pb(e);
	}
	ll krk(){
		ll sum=0;
		sort(all(G),[](edge a,edge b){
			return a.cost<b.cost;
		});
		UnionFind uf(n);
		rep(i,G.size()){
			edge e=G[i];
			if(!uf.findSet(e.from,e.to)){
				sum+=e.cost;
				tG[e.from].pb(pii(e.to,e.cost));
				tG[e.to].pb(pii(e.from,e.cost));
				uf.unionSet(e.from,e.to);
			}
		}
		return sum;
	}
	void dfs(ll a,ll b,ll c){
		rep(i,tG[a].size())if(used[tG[a][i].first]==0){
			used[tG[a][i].first]=true;
			ll t=max<ll>(b,tG[a][i].second);
			dp[c][tG[a][i].first]=t;
			dfs(tG[a][i].first,t,c);
		}
	}
	void solve(){
		tG=vvp(n);
		ll out=krk();
		dp=vvi(n,vi(n));
		rep(i,n){
			used=vi(n);
			used[i]=1;
			dfs(i,0,i);
		}
//		rep(i,n){rep(j,n)cout<<" "<<dp[i][j];cout<<endl;}
		
		ll q;
		cin>>q;
		while(q--){
			ll a,b;
			cin>>a>>b;
			a--;b--;
			cout<<out-dp[a][b]<<endl;
		}
	}
};
int main(){
	ll n,m;
	cin>>n>>m;
	KRK krk(n);
	while(m--){
		ll a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		krk.add_edge(a,b,c);
	}
	krk.solve();
}








### 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<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const ll inf=1e17;
struct UnionFind{
    vector<ll> data;
    UnionFind(ll size) : data(size, -1) {}
    bool unionSet(ll x,ll y){
        x=root(x);y=root(y);
        if(x==y)return 0;
        if(data[y]<data[x])swap(x,y);
        data[x]+=data[y],data[y]=x;
        return 1;
    }
    bool findSet(ll x,ll y){
        return root(x)==root(y);
    }
    ll root(ll x){
        return data[x]<0 ? x : data[x]=root(data[x]);
    }
    ll size(ll x){
        return -data[root(x)];
    }
};
class KRK{//c++11
	public:
	struct edge{
		ll from,to,cost;
	};
	vector<edge>G;
	vvp tG;
	vvi dp;
	vi used;
	ll n;
	KRK(ll size){
		n=size;
	}
	void add_edge(ll a,ll b,ll c){
		edge e={a,b,c};
		G.pb(e);
	}
	ll krk(){
		ll sum=0;
		sort(all(G),[](edge a,edge b){
			return a.cost<b.cost;
		});
		UnionFind uf(n);
		rep(i,G.size()){
			edge e=G[i];
			if(!uf.findSet(e.from,e.to)){
				sum+=e.cost;
				tG[e.from].pb(pii(e.to,e.cost));
				tG[e.to].pb(pii(e.from,e.cost));
				uf.unionSet(e.from,e.to);
			}
		}
		return sum;
	}
	void dfs(ll a,ll b,ll c){
		rep(i,tG[a].size())if(used[tG[a][i].first]==0){
			used[tG[a][i].first]=true;
			ll t=max<ll>(b,tG[a][i].second);
			dp[c][tG[a][i].first]=t;
			dfs(tG[a][i].first,t,c);
		}
	}
	void solve(){
		tG=vvp(n);
		ll out=krk();
		dp=vvi(n,vi(n));
		rep(i,n){
			used=vi(n);
			used[i]=1;
			dfs(i,0,i);
		}
//		rep(i,n){rep(j,n)cout<<" "<<dp[i][j];cout<<endl;}
		
		ll q;
		cin>>q;
		while(q--){
			ll a,b;
			cin>>a>>b;
			a--;b--;
			cout<<out-dp[a][b]<<endl;
		}
	}
};
int main(){
	ll n,m;
	cin>>n>>m;
	KRK krk(n);
	while(m--){
		ll a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		krk.add_edge(a,b,c);
	}
	krk.solve();
}








```