#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
typedef pair<int64_t,int64_t> P;
typedef pair<int64_t,P> T;
vector<P> G[4001];
int64_t ans[4001][4001]={};
class uft {//union-find tree
public:
    int parent[4010];
    int size[4010];
    int root(int x);
    bool same(int x,int y);
    void unite(int x,int y);
};
int uft::root(int x){
    if(parent[x]==x){
        return x;
    }
    return parent[x] = root(parent[x]);
}
bool uft::same(int x,int y){
    if(root(x)==root(y)){
        return true;
    }else{
        return false;
    }
}
void uft::unite(int x,int y){
    x=root(x);
    y=root(y);
    if(x == y) return;
    parent[x] = y;
    size[y] = size[y]+size[x];
}
int64_t Kruskal(priority_queue<T, vector<T>, greater<T> > q,int N){
    uft u;
    for(int i=0;i<N;i++){
        u.parent[i]=i;
        u.size[i]=1;
    }
    int64_t ret=0;
    while(u.size[u.root(0)] != N && !q.empty()){
        T edge = q.top(); q.pop();
        int s=(edge.second).first;
        int t=(edge.second).second;
        if(u.root(s) != u.root(t) ){
            u.unite(s,t);
            ret += edge.first;
            G[s].push_back(P(t,edge.first));
            G[t].push_back(P(s,edge.first));
            //cout<<s<<' '<<t<<' '<<edge.first<<endl;
        }
    }
    return ret;
}

int main(){
    int N,M;
    cin>>N>>M;
    priority_queue<T, vector<T>, greater<T> > q;
    for(int i=0;i<M;i++){
        int a,b;
        int64_t c;
        cin>>a>>b>>c;
        a--; b--;
        T d = T(c,P(a,b));
        q.push(d);
    }
    int64_t an=Kruskal(q,N);
    //cout<<an<<endl;
    for(int i=0;i<N;i++){
        bool used[4010]={};
        used[i]=true;
        queue<P> qu;
        qu.push(P(i,0));
        while (!qu.empty()) {
            P v  = qu.front(); qu.pop();
            //cout<< v.first <<' '<< v.second <<endl;
            for(int j=0;j<G[v.first].size();j++){
                P u = G[v.first][j];
                if(!used[u.first]){
                    //cout<<v.first<<' '<<v.second<<' '<<u.first<<' '<<u.second<<endl;
                    used[u.first]=true;
                    ans[i][u.first]=max(v.second,u.second);
                    //cout<<"ans "<<i<<' '<<u.first<<' '<<ans[i][u.first]<<endl;cout<<endl;
                    qu.push(P(u.first,ans[i][u.first]));
                }
            }
        }
    }/*
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout<<ans[i][j]<<' ';
        }cout<<endl;
    }*/
    int Q;
    cin>>Q;
    for(int i=0;i<Q;i++){
        int s,t;
        cin>>s>>t;
        s--;t--;
        cout<< an - ans[s][t] << endl;
    }
    
    
    return 0;
}

### Prompt

Your task is to create 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<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
typedef pair<int64_t,int64_t> P;
typedef pair<int64_t,P> T;
vector<P> G[4001];
int64_t ans[4001][4001]={};
class uft {//union-find tree
public:
    int parent[4010];
    int size[4010];
    int root(int x);
    bool same(int x,int y);
    void unite(int x,int y);
};
int uft::root(int x){
    if(parent[x]==x){
        return x;
    }
    return parent[x] = root(parent[x]);
}
bool uft::same(int x,int y){
    if(root(x)==root(y)){
        return true;
    }else{
        return false;
    }
}
void uft::unite(int x,int y){
    x=root(x);
    y=root(y);
    if(x == y) return;
    parent[x] = y;
    size[y] = size[y]+size[x];
}
int64_t Kruskal(priority_queue<T, vector<T>, greater<T> > q,int N){
    uft u;
    for(int i=0;i<N;i++){
        u.parent[i]=i;
        u.size[i]=1;
    }
    int64_t ret=0;
    while(u.size[u.root(0)] != N && !q.empty()){
        T edge = q.top(); q.pop();
        int s=(edge.second).first;
        int t=(edge.second).second;
        if(u.root(s) != u.root(t) ){
            u.unite(s,t);
            ret += edge.first;
            G[s].push_back(P(t,edge.first));
            G[t].push_back(P(s,edge.first));
            //cout<<s<<' '<<t<<' '<<edge.first<<endl;
        }
    }
    return ret;
}

int main(){
    int N,M;
    cin>>N>>M;
    priority_queue<T, vector<T>, greater<T> > q;
    for(int i=0;i<M;i++){
        int a,b;
        int64_t c;
        cin>>a>>b>>c;
        a--; b--;
        T d = T(c,P(a,b));
        q.push(d);
    }
    int64_t an=Kruskal(q,N);
    //cout<<an<<endl;
    for(int i=0;i<N;i++){
        bool used[4010]={};
        used[i]=true;
        queue<P> qu;
        qu.push(P(i,0));
        while (!qu.empty()) {
            P v  = qu.front(); qu.pop();
            //cout<< v.first <<' '<< v.second <<endl;
            for(int j=0;j<G[v.first].size();j++){
                P u = G[v.first][j];
                if(!used[u.first]){
                    //cout<<v.first<<' '<<v.second<<' '<<u.first<<' '<<u.second<<endl;
                    used[u.first]=true;
                    ans[i][u.first]=max(v.second,u.second);
                    //cout<<"ans "<<i<<' '<<u.first<<' '<<ans[i][u.first]<<endl;cout<<endl;
                    qu.push(P(u.first,ans[i][u.first]));
                }
            }
        }
    }/*
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout<<ans[i][j]<<' ';
        }cout<<endl;
    }*/
    int Q;
    cin>>Q;
    for(int i=0;i<Q;i++){
        int s,t;
        cin>>s>>t;
        s--;t--;
        cout<< an - ans[s][t] << endl;
    }
    
    
    return 0;
}

```