#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
#define N 4010
typedef pair<int,int> P;
typedef pair<int,pair<int,int> >PP;

ll primsum=0;
vector<P> v[N],u[N];
priority_queue<PP,vector<PP>,greater<PP> >Q;
void Qpush(int cost,int now,int from){
    Q.push(make_pair(cost,make_pair(now,from)));
}
void Prim(){
    bool vis[N]={0};
    Qpush(0,0,-1);
    while(!Q.empty()){
	int cost=Q.top().first;
	int x=Q.top().second.first;
	int from=Q.top().second.second;
	Q.pop();
	if(vis[x]==true)continue;
	vis[x]=true;
	if(from!=-1){
	    u[x].push_back(make_pair(cost,from));
	    u[from].push_back(make_pair(cost,x));
	    primsum+=cost;
	}
	lol(i,v[x].size()){
	    if(v[x][i].second==from)continue;
	    Qpush(v[x][i].first,v[x][i].second,x);
	}
    }
}

ll ans[N][N];
void DFS(int x,int maxi,int root,int from){
    ans[root][x]=maxi;
    lol(i,u[x].size()){
	if(u[x][i].second==from)continue;
	int cost=u[x][i].first;
	DFS(u[x][i].second,max(maxi,cost),root,x);
    }
}

int main(){
    int n,m,q;cin>>n>>m;
    lol(i,m){
	int a,b,c;cin>>a>>b>>c;a--,b--;
	v[a].push_back(make_pair(c,b));
	v[b].push_back(make_pair(c,a));
    }
    Prim();
    lol(i,n)DFS(i,0,i,-1);
    cin>>q;
    lol(i,q){
	int a,b;cin>>a>>b;a--,b--;
	cout<<primsum-ans[a][b]<<endl;
    }
    return 0;
}

### Prompt

Generate a CPP solution 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<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
#define N 4010
typedef pair<int,int> P;
typedef pair<int,pair<int,int> >PP;

ll primsum=0;
vector<P> v[N],u[N];
priority_queue<PP,vector<PP>,greater<PP> >Q;
void Qpush(int cost,int now,int from){
    Q.push(make_pair(cost,make_pair(now,from)));
}
void Prim(){
    bool vis[N]={0};
    Qpush(0,0,-1);
    while(!Q.empty()){
	int cost=Q.top().first;
	int x=Q.top().second.first;
	int from=Q.top().second.second;
	Q.pop();
	if(vis[x]==true)continue;
	vis[x]=true;
	if(from!=-1){
	    u[x].push_back(make_pair(cost,from));
	    u[from].push_back(make_pair(cost,x));
	    primsum+=cost;
	}
	lol(i,v[x].size()){
	    if(v[x][i].second==from)continue;
	    Qpush(v[x][i].first,v[x][i].second,x);
	}
    }
}

ll ans[N][N];
void DFS(int x,int maxi,int root,int from){
    ans[root][x]=maxi;
    lol(i,u[x].size()){
	if(u[x][i].second==from)continue;
	int cost=u[x][i].first;
	DFS(u[x][i].second,max(maxi,cost),root,x);
    }
}

int main(){
    int n,m,q;cin>>n>>m;
    lol(i,m){
	int a,b,c;cin>>a>>b>>c;a--,b--;
	v[a].push_back(make_pair(c,b));
	v[b].push_back(make_pair(c,a));
    }
    Prim();
    lol(i,n)DFS(i,0,i,-1);
    cin>>q;
    lol(i,q){
	int a,b;cin>>a>>b;a--,b--;
	cout<<primsum-ans[a][b]<<endl;
    }
    return 0;
}

```