#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;

class UnionFind{
public:
    int n, c;
    vector<int> par;
    UnionFind(int n) : n(n), c(0), par(n, -1){}
    int Find(int x){return par[x] < 0 ? x : Find(par[x]);}
    bool Unite(int x, int y){
        if((x = Find(x)) == (y = Find(y)))
            return false;
        if(par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
        ++c;
        return true;
    }
};

signed main(){
    int n, m, q;
    cin >> n >> m;
    vector<vector<pair<int,int>>> edges(n);
    priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> que;
    for(int i = 0; i < m; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        edges[--a].emplace_back(--b, c);
        edges[b].emplace_back(a, c);
        que.emplace(c, make_pair(a, b));
    }
    i64 mst_cost = 0;
    UnionFind uni(n);
    vector<vector<pair<int,int>>> tr(n);
    while(uni.c != n - 1){
        int cost;
        pair<int,int> p;
        tie(cost, p) = que.top();
        que.pop();
        if(uni.Unite(p.first, p.second)){
            mst_cost += cost;
            tr[p.first].emplace_back(p.second, cost);
            tr[p.second].emplace_back(p.first, cost);
        }
    }
    vector<vector<int>> v(n, vector<int>(n, -1));
    function<void(int,int, int)> max_cost = [&](int from, int pos, int ma){
        for(auto& e : tr[pos]){
            if(v[from][e.first] == -1){
                int nex = max(e.second, ma);
                v[from][e.first] = nex;
                max_cost(from, e.first, nex);
            }
        }
    };
    for(int i = 0; i < n; ++i){
        v[i][i] = 0;
        max_cost(i, i, 0);
    }
    cin >> q;
    for(int i = 0; i < q; ++i){
        int s, t;
        cin >> s >> t;
        cout << mst_cost - v[--s][--t] << endl;
    }
}

### Prompt

Please formulate 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;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;

class UnionFind{
public:
    int n, c;
    vector<int> par;
    UnionFind(int n) : n(n), c(0), par(n, -1){}
    int Find(int x){return par[x] < 0 ? x : Find(par[x]);}
    bool Unite(int x, int y){
        if((x = Find(x)) == (y = Find(y)))
            return false;
        if(par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
        ++c;
        return true;
    }
};

signed main(){
    int n, m, q;
    cin >> n >> m;
    vector<vector<pair<int,int>>> edges(n);
    priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> que;
    for(int i = 0; i < m; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        edges[--a].emplace_back(--b, c);
        edges[b].emplace_back(a, c);
        que.emplace(c, make_pair(a, b));
    }
    i64 mst_cost = 0;
    UnionFind uni(n);
    vector<vector<pair<int,int>>> tr(n);
    while(uni.c != n - 1){
        int cost;
        pair<int,int> p;
        tie(cost, p) = que.top();
        que.pop();
        if(uni.Unite(p.first, p.second)){
            mst_cost += cost;
            tr[p.first].emplace_back(p.second, cost);
            tr[p.second].emplace_back(p.first, cost);
        }
    }
    vector<vector<int>> v(n, vector<int>(n, -1));
    function<void(int,int, int)> max_cost = [&](int from, int pos, int ma){
        for(auto& e : tr[pos]){
            if(v[from][e.first] == -1){
                int nex = max(e.second, ma);
                v[from][e.first] = nex;
                max_cost(from, e.first, nex);
            }
        }
    };
    for(int i = 0; i < n; ++i){
        v[i][i] = 0;
        max_cost(i, i, 0);
    }
    cin >> q;
    for(int i = 0; i < q; ++i){
        int s, t;
        cin >> s >> t;
        cout << mst_cost - v[--s][--t] << endl;
    }
}

```