#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(_vs) for(auto _x : _vs){cout << _x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;} cout << endl;
#define printP(_p) cout << _p.first << " " << _p.second << endl
#define printVP(_vp) for(auto _p : _vp) printP(_p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;

class UnionFind {
private:
    const int n;
    vector<int> uni;
public:
    UnionFind(int _n) : n(_n), uni(_n, -1) {}
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
        return true;
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

struct edge {
    int from, to, cost;
    edge(){}
    edge(int _from, int _to, int _cost) : from(_from), to(_to), cost(_cost) {}
    bool operator< (const edge& e) const {
        return cost == e.cost ? (from == e.from ? to < e.to : from < e.from) : cost < e.cost;
    }
};

class Kruskal {
private:
    int n;
    vector<edge> edges;
    UnionFind uf;
public:
    Kruskal(int _n) : n(_n), uf(_n) {}
    void addEdge(int _from, int _to, int _cost) {
        edges.emplace_back(_from, _to, _cost);
    }
    pair<int, vector<edge>> calc() {
        sort(all(edges));
        int res = 0;
        vector<edge> selected_edges;
        rep(i, edges.size()) {
            if (uf.unite(edges[i].from, edges[i].to)) {
                res += edges[i].cost;
                selected_edges.emplace_back(edges[i]);
            }
        }
        return make_pair(res, selected_edges);
    }
};

// a.cpp

int ma[4001][4001];
typedef vector<vector<Pii>> Graph; // Pii = {to, cost}

void dfs(const Graph& G, int s, int now, int pre, int ma_cost) {
    ma[s][now] = ma_cost;
    for (auto e : G[now]) {
        if (e.first == pre) continue;
        dfs(G, s, e.first, now, max(e.second, ma_cost));
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m;
    cin >> n >> m;
    Kruskal ks(n);
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        ks.addEdge(a, b, c);
    }

    int cost;
    vector<edge> edges;
    tie(cost, edges) = ks.calc();

    Graph G(n);
    rep(i, edges.size()) {
        G[edges[i].from].emplace_back(edges[i].to, edges[i].cost);
        G[edges[i].to].emplace_back(edges[i].from, edges[i].cost);
    }

    rep(i, n) {
        dfs(G, i, i, -1, 0);
    }

    int Q;
    cin >> Q;
    rep(i, Q) {
        int s, t;
        cin >> s >> t;
        s--, t--;
        cout << cost - ma[s][t] << endl;
    }


}

### Prompt

Generate 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 rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(_vs) for(auto _x : _vs){cout << _x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;} cout << endl;
#define printP(_p) cout << _p.first << " " << _p.second << endl
#define printVP(_vp) for(auto _p : _vp) printP(_p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;

class UnionFind {
private:
    const int n;
    vector<int> uni;
public:
    UnionFind(int _n) : n(_n), uni(_n, -1) {}
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
        return true;
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

struct edge {
    int from, to, cost;
    edge(){}
    edge(int _from, int _to, int _cost) : from(_from), to(_to), cost(_cost) {}
    bool operator< (const edge& e) const {
        return cost == e.cost ? (from == e.from ? to < e.to : from < e.from) : cost < e.cost;
    }
};

class Kruskal {
private:
    int n;
    vector<edge> edges;
    UnionFind uf;
public:
    Kruskal(int _n) : n(_n), uf(_n) {}
    void addEdge(int _from, int _to, int _cost) {
        edges.emplace_back(_from, _to, _cost);
    }
    pair<int, vector<edge>> calc() {
        sort(all(edges));
        int res = 0;
        vector<edge> selected_edges;
        rep(i, edges.size()) {
            if (uf.unite(edges[i].from, edges[i].to)) {
                res += edges[i].cost;
                selected_edges.emplace_back(edges[i]);
            }
        }
        return make_pair(res, selected_edges);
    }
};

// a.cpp

int ma[4001][4001];
typedef vector<vector<Pii>> Graph; // Pii = {to, cost}

void dfs(const Graph& G, int s, int now, int pre, int ma_cost) {
    ma[s][now] = ma_cost;
    for (auto e : G[now]) {
        if (e.first == pre) continue;
        dfs(G, s, e.first, now, max(e.second, ma_cost));
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m;
    cin >> n >> m;
    Kruskal ks(n);
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        ks.addEdge(a, b, c);
    }

    int cost;
    vector<edge> edges;
    tie(cost, edges) = ks.calc();

    Graph G(n);
    rep(i, edges.size()) {
        G[edges[i].from].emplace_back(edges[i].to, edges[i].cost);
        G[edges[i].to].emplace_back(edges[i].from, edges[i].cost);
    }

    rep(i, n) {
        dfs(G, i, i, -1, 0);
    }

    int Q;
    cin >> Q;
    rep(i, Q) {
        int s, t;
        cin >> s >> t;
        s--, t--;
        cout << cost - ma[s][t] << endl;
    }


}

```