#include <bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
int parent[4005][4005];

struct path{
    int from;
    int to;
    ll cost;
};

struct UnionFind {
    vector<int> par;
    vector<int> rank;

    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0;
    }

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

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};

bool comp(path a, path b){
    if(a.cost > b.cost){
        return true;
    }
    return false;
}

int main() {
    //cout.precision(10);
    int n, m;
    cin >> n >> m;
    vector<path> pathes;
    for(int i = 0; i < m; i++){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        struct path in;
        in.from = a;
        in.to = b;
        in.cost = c;
        pathes.push_back(in);
    }
    sort(pathes.begin(), pathes.end(), comp);
    ll cost[4005];
    UnionFind uni(n + 1);
    ll sum = 0;
    for(int time = 1; time <= n - 1; time++){
        path test;
        while(true){
            test = pathes.back();
            pathes.pop_back();
            if(uni.issame(test.from, test.to)){
                continue;
            }
            break;
        }
        cost[time] = test.cost;
        sum += cost[time];
        uni.merge(test.from, test.to);
        for(int i = 1; i <= n; i++){
            uni.root(i);
        }
        for(int i = 1; i <= n; i++){
            parent[time][i] = uni.root(i);
        }
    }
    int q;
    cin >> q;
    for(int time = 1; time <= q; time++){
        int s, t;
        cin >> s >> t;
        int ok = n - 1;
        int ng = 0;
        while(ok - ng > 1){
            int mid = (ok + ng) / 2;
            if(parent[mid][s] == parent[mid][t]){
                ok = mid;
            } else {
                ng = mid;
            }
        }
        cout << sum - cost[ok] << endl;
    }
    return 0;
}
### Prompt

Create a solution in Cpp for 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;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
int parent[4005][4005];

struct path{
    int from;
    int to;
    ll cost;
};

struct UnionFind {
    vector<int> par;
    vector<int> rank;

    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0;
    }

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

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};

bool comp(path a, path b){
    if(a.cost > b.cost){
        return true;
    }
    return false;
}

int main() {
    //cout.precision(10);
    int n, m;
    cin >> n >> m;
    vector<path> pathes;
    for(int i = 0; i < m; i++){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        struct path in;
        in.from = a;
        in.to = b;
        in.cost = c;
        pathes.push_back(in);
    }
    sort(pathes.begin(), pathes.end(), comp);
    ll cost[4005];
    UnionFind uni(n + 1);
    ll sum = 0;
    for(int time = 1; time <= n - 1; time++){
        path test;
        while(true){
            test = pathes.back();
            pathes.pop_back();
            if(uni.issame(test.from, test.to)){
                continue;
            }
            break;
        }
        cost[time] = test.cost;
        sum += cost[time];
        uni.merge(test.from, test.to);
        for(int i = 1; i <= n; i++){
            uni.root(i);
        }
        for(int i = 1; i <= n; i++){
            parent[time][i] = uni.root(i);
        }
    }
    int q;
    cin >> q;
    for(int time = 1; time <= q; time++){
        int s, t;
        cin >> s >> t;
        int ok = n - 1;
        int ng = 0;
        while(ok - ng > 1){
            int mid = (ok + ng) / 2;
            if(parent[mid][s] == parent[mid][t]){
                ok = mid;
            } else {
                ng = mid;
            }
        }
        cout << sum - cost[ok] << endl;
    }
    return 0;
}
```