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

struct UnionFind {
    vector<long long> par;
    vector<long long> rank;
    vector<long long> time;
    const long long INF = 1e18;

    void initialize(long long n){
        par.resize(n);
        rank.resize(n);
        time.resize(n);
        for(long long i=0; i<n; i++){
            par[i] = i;
            rank[i] = 0;
            time[i] = INF;
        }
    }

    long long find(long long x, long long t){
        if(time[x] > t){
            return x;
        }else{
            return find(par[x], t);
        }
    }

    void unite(long long x, long long y, long long t){
        x = find(x, t);
        y = find(y, t);
        if(x == y) return;
        if(rank[x] < rank[y]){
            par[x] = y;
            time[x] = t;
        }else{
            par[y] = x;
            time[y] = t;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    bool same(long long x, long long y, long long t){
        return find(x, t) == find(y, t);
    }
};

struct edge{long long u, v, cost;};
bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

UnionFind uf;

long long kruskal(long long N, vector<edge> es){
    sort(es.begin(), es.end(), comp);
    uf.initialize(N);
    long long res = 0;
    for(long long i=0; i<es.size(); i++){
        edge e = es[i];
        if(!uf.same(e.u, e.v, e.cost)){
            uf.unite(e.u, e.v, e.cost);
            res += e.cost;
        }
    }
    return res;
}


int main(){
    long long i, j, k;
    long long N, M;
    cin >> N >> M;
    vector<edge> es;
    for(i=0; i<M; i++){
        long long a, b, c;
        cin >> a >> b >> c;
        es.push_back({a, b, c});
    }
    long long sum = kruskal(N+1, es);

    long long Q;
    cin >> Q;
    for(i=0; i<Q; i++){
        long long s, t;
        cin >> s >> t;
        long long ok=0, ng=1e10; 
        while(ng-ok>1){
            long long mid = (ng+ok)/2;
            if(uf.same(s, t, mid)){
                ng = mid;
            }else{
                ok = mid;
            }
        }
        cout << (sum-ok-1) << endl;
    }
    return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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;

struct UnionFind {
    vector<long long> par;
    vector<long long> rank;
    vector<long long> time;
    const long long INF = 1e18;

    void initialize(long long n){
        par.resize(n);
        rank.resize(n);
        time.resize(n);
        for(long long i=0; i<n; i++){
            par[i] = i;
            rank[i] = 0;
            time[i] = INF;
        }
    }

    long long find(long long x, long long t){
        if(time[x] > t){
            return x;
        }else{
            return find(par[x], t);
        }
    }

    void unite(long long x, long long y, long long t){
        x = find(x, t);
        y = find(y, t);
        if(x == y) return;
        if(rank[x] < rank[y]){
            par[x] = y;
            time[x] = t;
        }else{
            par[y] = x;
            time[y] = t;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    bool same(long long x, long long y, long long t){
        return find(x, t) == find(y, t);
    }
};

struct edge{long long u, v, cost;};
bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

UnionFind uf;

long long kruskal(long long N, vector<edge> es){
    sort(es.begin(), es.end(), comp);
    uf.initialize(N);
    long long res = 0;
    for(long long i=0; i<es.size(); i++){
        edge e = es[i];
        if(!uf.same(e.u, e.v, e.cost)){
            uf.unite(e.u, e.v, e.cost);
            res += e.cost;
        }
    }
    return res;
}


int main(){
    long long i, j, k;
    long long N, M;
    cin >> N >> M;
    vector<edge> es;
    for(i=0; i<M; i++){
        long long a, b, c;
        cin >> a >> b >> c;
        es.push_back({a, b, c});
    }
    long long sum = kruskal(N+1, es);

    long long Q;
    cin >> Q;
    for(i=0; i<Q; i++){
        long long s, t;
        cin >> s >> t;
        long long ok=0, ng=1e10; 
        while(ng-ok>1){
            long long mid = (ng+ok)/2;
            if(uf.same(s, t, mid)){
                ng = mid;
            }else{
                ok = mid;
            }
        }
        cout << (sum-ok-1) << endl;
    }
    return 0;
}
```