#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=4003,INF=1<<30;
ll dis[MAX][MAX];
vector<pair<int,ll>> G[MAX];
int V;

struct edge{int from,to;ll dis;};

bool compare(edge a,edge b){
    return a.dis<b.dis;
}

int par[MAX];

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

int root(int a){
    if(par[a]==a) return a;
    else return par[a]=root(par[a]);
}

void unite(int a,int b){
    if(root(a)!=root(b)) par[root(b)]=root(a);
}

bool check(int a,int b){
    return root(a)==root(b);
}

void BFS(){
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            dis[i][j]=-1;
        }
        dis[i][i]=0;
        queue<int> Q;
        Q.push(i);
        
        while(!Q.empty()){
            int a=Q.front();Q.pop();
            for(int k=0;k<G[a].size();k++){
                int b=G[a][k].first;
                ll c=G[a][k].second;
                
                if(dis[i][b]!=-1) continue;
                
                dis[i][b]=max(dis[i][a],c);
                Q.push(b);
            }
        }
    }
}


int main(){
    
    int E;cin>>V>>E;
    vector<edge> S(E);
    for(int i=0;i<E;i++){
        int a,b;
        ll c;cin>>a>>b>>c;
        a--;b--;
        S[i]={a,b,c};
    }
    
    sort(all(S),compare);
    
    init(V);
    
    ll sum=0;
    
    for(int i=0;i<E;i++){
        int a=S[i].from,b=S[i].to;
        ll c=S[i].dis;
        if(check(a,b)) continue;
        unite(a,b);
        sum+=c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    
    BFS();
    
    int Q;cin>>Q;
    while(Q){
        int a,b;cin>>a>>b;
        a--;b--;
        cout<<sum-dis[a][b]<<endl;
        
        Q--;
    }
    
}


### 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;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=4003,INF=1<<30;
ll dis[MAX][MAX];
vector<pair<int,ll>> G[MAX];
int V;

struct edge{int from,to;ll dis;};

bool compare(edge a,edge b){
    return a.dis<b.dis;
}

int par[MAX];

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

int root(int a){
    if(par[a]==a) return a;
    else return par[a]=root(par[a]);
}

void unite(int a,int b){
    if(root(a)!=root(b)) par[root(b)]=root(a);
}

bool check(int a,int b){
    return root(a)==root(b);
}

void BFS(){
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            dis[i][j]=-1;
        }
        dis[i][i]=0;
        queue<int> Q;
        Q.push(i);
        
        while(!Q.empty()){
            int a=Q.front();Q.pop();
            for(int k=0;k<G[a].size();k++){
                int b=G[a][k].first;
                ll c=G[a][k].second;
                
                if(dis[i][b]!=-1) continue;
                
                dis[i][b]=max(dis[i][a],c);
                Q.push(b);
            }
        }
    }
}


int main(){
    
    int E;cin>>V>>E;
    vector<edge> S(E);
    for(int i=0;i<E;i++){
        int a,b;
        ll c;cin>>a>>b>>c;
        a--;b--;
        S[i]={a,b,c};
    }
    
    sort(all(S),compare);
    
    init(V);
    
    ll sum=0;
    
    for(int i=0;i<E;i++){
        int a=S[i].from,b=S[i].to;
        ll c=S[i].dis;
        if(check(a,b)) continue;
        unite(a,b);
        sum+=c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    
    BFS();
    
    int Q;cin>>Q;
    while(Q){
        int a,b;cin>>a>>b;
        a--;b--;
        cout<<sum-dis[a][b]<<endl;
        
        Q--;
    }
    
}


```