#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, ll> P;

vector< vector<P> > G;

struct Union_Find {
    //各要素が属する集合の代表(根)を管理する
    //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい
    vector<int> data;
    
    Union_Find(int size) : data(size, -1) {}
    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return is_union;
    }
    int Find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            return data[x];
        }
    }
    bool same(int x, int y) {
        return Find(x) == Find(y);
    }
    int size(int x) {
        return -data[Find(x)];
    }
};

struct Edge {
    int u, v;
    ll cost;
    bool operator<(const Edge& e) const {
        return cost < e.cost;
    }
}; 

struct Graph {
    int n; //頂点数
    vector<Edge> es; //辺集合
    
    ll kruskal() {
        sort(es.begin(), es.end());
        Union_Find uf(n);
        ll min_cost = 0;
        for(int i = 0; i < (int)es.size(); i++) {
            Edge e = es[i];
            if (!uf.same(e.u, e.v)) {
                min_cost += e.cost;
                uf.Union(e.u, e.v);
                G[e.u].emplace_back(e.v, e.cost);
                G[e.v].emplace_back(e.u, e.cost);
            }
        }
        return min_cost;
    }
};

Graph input() {
   Graph g;
   int m;
   cin >> g.n >> m;
   g.es = vector<Edge>(m);
   for(int i = 0; i < m; i++) {
        cin >> g.es[i].u >> g.es[i].v >> g.es[i].cost;
        g.es[i].u--;
        g.es[i].v--;
   }
   return g;
}

void dfs(int cur, int par, vector<ll>& d) {
    for (P nex : G[cur]) {
        if (nex.first == par) continue;
        d[nex.first] = max(d[cur], nex.second);
        dfs(nex.first, cur, d);
    }
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	Graph g = input();
    G.resize(g.n);
    ll sum = g.kruskal();
    vector< vector<ll> > maxc(g.n, vector<ll>(g.n, 0));
    for (int i = 0; i < g.n; i++) {
        dfs(i, -1, maxc[i]);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        cout << sum - maxc[s][t] << endl;
    }
	return 0;
}
### Prompt

In CPP, your task is to solve 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 ll;
typedef pair<int, ll> P;

vector< vector<P> > G;

struct Union_Find {
    //各要素が属する集合の代表(根)を管理する
    //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい
    vector<int> data;
    
    Union_Find(int size) : data(size, -1) {}
    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return is_union;
    }
    int Find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            return data[x];
        }
    }
    bool same(int x, int y) {
        return Find(x) == Find(y);
    }
    int size(int x) {
        return -data[Find(x)];
    }
};

struct Edge {
    int u, v;
    ll cost;
    bool operator<(const Edge& e) const {
        return cost < e.cost;
    }
}; 

struct Graph {
    int n; //頂点数
    vector<Edge> es; //辺集合
    
    ll kruskal() {
        sort(es.begin(), es.end());
        Union_Find uf(n);
        ll min_cost = 0;
        for(int i = 0; i < (int)es.size(); i++) {
            Edge e = es[i];
            if (!uf.same(e.u, e.v)) {
                min_cost += e.cost;
                uf.Union(e.u, e.v);
                G[e.u].emplace_back(e.v, e.cost);
                G[e.v].emplace_back(e.u, e.cost);
            }
        }
        return min_cost;
    }
};

Graph input() {
   Graph g;
   int m;
   cin >> g.n >> m;
   g.es = vector<Edge>(m);
   for(int i = 0; i < m; i++) {
        cin >> g.es[i].u >> g.es[i].v >> g.es[i].cost;
        g.es[i].u--;
        g.es[i].v--;
   }
   return g;
}

void dfs(int cur, int par, vector<ll>& d) {
    for (P nex : G[cur]) {
        if (nex.first == par) continue;
        d[nex.first] = max(d[cur], nex.second);
        dfs(nex.first, cur, d);
    }
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	Graph g = input();
    G.resize(g.n);
    ll sum = g.kruskal();
    vector< vector<ll> > maxc(g.n, vector<ll>(g.n, 0));
    for (int i = 0; i < g.n; i++) {
        dfs(i, -1, maxc[i]);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        cout << sum - maxc[s][t] << endl;
    }
	return 0;
}
```