#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

class UnionFind {
    int cnt;
    vector<int> par, rank, size;
public:
    UnionFind() {}
    UnionFind(int _n) :cnt(_n), par(_n), rank(_n), size(_n, 1) {
        for (int i = 0; i<_n; ++i) par[i] = i;
    }
    int find(int k) {
        return (k == par[k]) ? k : (par[k] = find(par[k]));
    }
    int operator[](int k) {
        return find(k);
    }
    int getSize(int k) {
        return size[find(k)];
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        --cnt;
        if (rank[x] < rank[y]) {
            par[x] = y;
            size[y] += size[x];
        } else {
            par[y] = x;
            size[x] += size[y];
            if (rank[y] == rank[x]) ++rank[x];
        }
    }
    int count() {
        return cnt;
    }
};

template<class Weight>
struct KruskalMST {
    using Edges = vector<tuple<Weight, int, int>>;
    Weight sum;
    Edges mst;
    KruskalMST(int V, Edges edges) :sum(0) {
        sort(edges.begin(), edges.end());
        UnionFind uf(V);
        each(e, edges) {
            Weight w;
            int u, v;
            tie(w, u, v) = e;
            if (uf[u] != uf[v]) {
                mst.emplace_back(e);
                uf.unite(u, v);
                sum += w;
            }
        }
    }
};

int N, M, ma[4001][4001];
vector<pii> G[4001];

void dfs(int u, int s, int p=-1, int x=0) {
    ma[s][u] = x;
    each(e, G[u]) {
        if (e.first != p) {
            dfs(e.first, s, u, max(x, e.second));
        }
    }
}

void solve() {
    cin >> N >> M;

    vector<tuple<ll, int, int>> E(M);
    rep(i, M) {
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        E[i] = tie(c, a, b);
    }

    auto mst = KruskalMST<ll>(N, E);
    each(e, mst.mst) {
        ll ww;
        int w, u, v;
        tie(ww, u, v) = e;
        w = (int)ww;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    rep(i, N)dfs(i, i);

    int Q;
    cin >> Q;
    rep(i, Q) {
        int s, t;
        cin >> s >> t;
        --s; --t;
        ll ans = mst.sum - ma[s][t];
        cout << ans << endl;
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

class UnionFind {
    int cnt;
    vector<int> par, rank, size;
public:
    UnionFind() {}
    UnionFind(int _n) :cnt(_n), par(_n), rank(_n), size(_n, 1) {
        for (int i = 0; i<_n; ++i) par[i] = i;
    }
    int find(int k) {
        return (k == par[k]) ? k : (par[k] = find(par[k]));
    }
    int operator[](int k) {
        return find(k);
    }
    int getSize(int k) {
        return size[find(k)];
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        --cnt;
        if (rank[x] < rank[y]) {
            par[x] = y;
            size[y] += size[x];
        } else {
            par[y] = x;
            size[x] += size[y];
            if (rank[y] == rank[x]) ++rank[x];
        }
    }
    int count() {
        return cnt;
    }
};

template<class Weight>
struct KruskalMST {
    using Edges = vector<tuple<Weight, int, int>>;
    Weight sum;
    Edges mst;
    KruskalMST(int V, Edges edges) :sum(0) {
        sort(edges.begin(), edges.end());
        UnionFind uf(V);
        each(e, edges) {
            Weight w;
            int u, v;
            tie(w, u, v) = e;
            if (uf[u] != uf[v]) {
                mst.emplace_back(e);
                uf.unite(u, v);
                sum += w;
            }
        }
    }
};

int N, M, ma[4001][4001];
vector<pii> G[4001];

void dfs(int u, int s, int p=-1, int x=0) {
    ma[s][u] = x;
    each(e, G[u]) {
        if (e.first != p) {
            dfs(e.first, s, u, max(x, e.second));
        }
    }
}

void solve() {
    cin >> N >> M;

    vector<tuple<ll, int, int>> E(M);
    rep(i, M) {
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        E[i] = tie(c, a, b);
    }

    auto mst = KruskalMST<ll>(N, E);
    each(e, mst.mst) {
        ll ww;
        int w, u, v;
        tie(ww, u, v) = e;
        w = (int)ww;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    rep(i, N)dfs(i, i);

    int Q;
    cin >> Q;
    rep(i, Q) {
        int s, t;
        cin >> s >> t;
        --s; --t;
        ll ans = mst.sum - ma[s][t];
        cout << ans << endl;
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}
```