#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int N,M;
vpint G[4444];

int A[444444],B[444444],C[444444];

int cost[4444][4444];

void dfs(int v,int p,int c,int s){
    cost[s][v]=c;
    for(auto &e:G[v]){
        if(e.fi==p)continue;
        dfs(e.fi,v,max(c,e.se),s);
    }
}

signed main(){
    cin>>N>>M;

    vpint ord;
    rep(i,M){
        cin>>A[i]>>B[i]>>C[i];
        A[i]--;B[i]--;
        ord.pb({C[i],i});
    }
    sort(all(ord));

    int sum=0;
    UnionFindTree uf(N);
    rep(i,M){
        int w=ord[i].se;
        if(uf.areSame(A[w],B[w]))continue;
        uf.unite(A[w],B[w]);
        G[A[w]].pb({B[w],C[w]});
        G[B[w]].pb({A[w],C[w]});
        sum+=C[w];
    }

    rep(i,N)dfs(i,-1,0,i);

    int Q;cin>>Q;
    while(Q--){
        int a,b;
        cin>>a>>b;
        a--;b--;
        cout<<sum-cost[a][b]<<endl;
    }
    return 0;
}

### Prompt

Please formulate 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<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int N,M;
vpint G[4444];

int A[444444],B[444444],C[444444];

int cost[4444][4444];

void dfs(int v,int p,int c,int s){
    cost[s][v]=c;
    for(auto &e:G[v]){
        if(e.fi==p)continue;
        dfs(e.fi,v,max(c,e.se),s);
    }
}

signed main(){
    cin>>N>>M;

    vpint ord;
    rep(i,M){
        cin>>A[i]>>B[i]>>C[i];
        A[i]--;B[i]--;
        ord.pb({C[i],i});
    }
    sort(all(ord));

    int sum=0;
    UnionFindTree uf(N);
    rep(i,M){
        int w=ord[i].se;
        if(uf.areSame(A[w],B[w]))continue;
        uf.unite(A[w],B[w]);
        G[A[w]].pb({B[w],C[w]});
        G[B[w]].pb({A[w],C[w]});
        sum+=C[w];
    }

    rep(i,N)dfs(i,-1,0,i);

    int Q;cin>>Q;
    while(Q--){
        int a,b;
        cin>>a>>b;
        a--;b--;
        cout<<sum-cost[a][b]<<endl;
    }
    return 0;
}

```