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

using ll = long long;

class union_find {
public:
    union_find(int n) : par(n, -1) {}

    int root(int x) {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }

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

private:
    std::vector<int> par;
};

struct edge {
    int from, to;
    ll cost;
    edge(int f, int t, ll c) : from(f), to(t), cost(c) {}

    bool operator<(const edge& that) const {
        return cost < that.cost;
    }
};

using edges = vector<edge>;
using graph = vector<edges>;

constexpr int inf = 1e9;

int main() {
    int n, m; cin >> n >> m;
    edges es;
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        es.emplace_back(a - 1, b - 1, c);
    }
    sort(begin(es), end(es));

    union_find uf(n);
    graph g(n);
    ll ans = 0;
    for(const auto& e : es) {
        if(uf.unite(e.from, e.to)) {
            ans += e.cost;
            g[e.from].emplace_back(e.from, e.to, e.cost);
            g[e.to].emplace_back(e.to, e.from, e.cost);
        }
    }

    vector<vector<int>> ma(n, vector<int>(n, inf));
    for(int s = 0; s < n; ++s) {
        function<void(int, int, int)> dfs = [&] (int v, int p, int cur) {
            ma[s][v] = cur;
            for(auto const& e : g[v]) {
                if(e.to == p) continue;
                dfs(e.to, v, max(cur, (int)e.cost));
            }
        };
        dfs(s, -1, 0);
    }

    int q; cin >> q;
    while(q--) {
        int s, t; cin >> s >> t;
        cout << ans - ma[s - 1][t - 1] << endl;
    }
}
### 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;

using ll = long long;

class union_find {
public:
    union_find(int n) : par(n, -1) {}

    int root(int x) {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }

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

private:
    std::vector<int> par;
};

struct edge {
    int from, to;
    ll cost;
    edge(int f, int t, ll c) : from(f), to(t), cost(c) {}

    bool operator<(const edge& that) const {
        return cost < that.cost;
    }
};

using edges = vector<edge>;
using graph = vector<edges>;

constexpr int inf = 1e9;

int main() {
    int n, m; cin >> n >> m;
    edges es;
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        es.emplace_back(a - 1, b - 1, c);
    }
    sort(begin(es), end(es));

    union_find uf(n);
    graph g(n);
    ll ans = 0;
    for(const auto& e : es) {
        if(uf.unite(e.from, e.to)) {
            ans += e.cost;
            g[e.from].emplace_back(e.from, e.to, e.cost);
            g[e.to].emplace_back(e.to, e.from, e.cost);
        }
    }

    vector<vector<int>> ma(n, vector<int>(n, inf));
    for(int s = 0; s < n; ++s) {
        function<void(int, int, int)> dfs = [&] (int v, int p, int cur) {
            ma[s][v] = cur;
            for(auto const& e : g[v]) {
                if(e.to == p) continue;
                dfs(e.to, v, max(cur, (int)e.cost));
            }
        };
        dfs(s, -1, 0);
    }

    int q; cin >> q;
    while(q--) {
        int s, t; cin >> s >> t;
        cout << ans - ma[s - 1][t - 1] << endl;
    }
}
```