#include <bits/stdc++.h>
using namespace std;
#define VI vector<int>

void dfs(int node, int f, vector<VI> &G, vector<VI> &C, VI &d, int val) {
    d[node] = val;
    for(int i = 0; i < int(G[node].size()); ++i) {
        int temp = G[node][i];
        if(temp == f)
            continue;
        dfs(temp, node, G, C, d, max(val, C[node][i]));
    }
}

int main() {
    //ifstream cin("testA.in");

    int n, m; cin >> n >> m;
    vector<int> a(m, 0), b(m, 0), c(m, 0);
    vector<pair<int, int>> edges;

    for(int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
    }

    for(int i = 0; i < m; ++i) {
        edges.push_back({c[i], i});
    }

    sort(edges.begin(), edges.end());

    vector<int> dad(n, 0), sz(n, 0);
    for(int i = 0; i < n; ++i)
        dad[i] = i;

    auto f = [&] (int x) {
        int root = x;
        int steps = 0;
        while(root != dad[root]) {
            root = dad[root];
            ++steps;
        }
        while(x != root) {
            int temp = dad[x];
            dad[x] = root;
            x = temp;
        }
        return root;
    };

    auto unite = [&] (int a, int b) {
        dad[a] = b;
    };
    
    vector<vector<int>> G(n), C(n);
    long long ans = 0;

    for(auto edge : edges) {
        int x = a[edge.second];
        int y = b[edge.second];
        if(f(x) != f(y)) {
            ans += edge.first;
            unite(f(x), f(y));
            G[x].push_back(y);
            G[y].push_back(x);
            C[x].push_back(edge.first);
            C[y].push_back(edge.first);
        }
    }
        
    vector<vector<int>> d(n, vector<int> (n, 0));
    
    for(int i = 0; i < n; ++i) {
        int now = 0;
        dfs(i, -1, G, C, d[i], now);
    }

    int q; cin >> q;
    for(int i = 0; i < q; ++i) {
        int x, y; cin >> x >> y;
        x--;y--;
        cout << ans - d[x][y] << "\n";
    }
}
### 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;
#define VI vector<int>

void dfs(int node, int f, vector<VI> &G, vector<VI> &C, VI &d, int val) {
    d[node] = val;
    for(int i = 0; i < int(G[node].size()); ++i) {
        int temp = G[node][i];
        if(temp == f)
            continue;
        dfs(temp, node, G, C, d, max(val, C[node][i]));
    }
}

int main() {
    //ifstream cin("testA.in");

    int n, m; cin >> n >> m;
    vector<int> a(m, 0), b(m, 0), c(m, 0);
    vector<pair<int, int>> edges;

    for(int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
    }

    for(int i = 0; i < m; ++i) {
        edges.push_back({c[i], i});
    }

    sort(edges.begin(), edges.end());

    vector<int> dad(n, 0), sz(n, 0);
    for(int i = 0; i < n; ++i)
        dad[i] = i;

    auto f = [&] (int x) {
        int root = x;
        int steps = 0;
        while(root != dad[root]) {
            root = dad[root];
            ++steps;
        }
        while(x != root) {
            int temp = dad[x];
            dad[x] = root;
            x = temp;
        }
        return root;
    };

    auto unite = [&] (int a, int b) {
        dad[a] = b;
    };
    
    vector<vector<int>> G(n), C(n);
    long long ans = 0;

    for(auto edge : edges) {
        int x = a[edge.second];
        int y = b[edge.second];
        if(f(x) != f(y)) {
            ans += edge.first;
            unite(f(x), f(y));
            G[x].push_back(y);
            G[y].push_back(x);
            C[x].push_back(edge.first);
            C[y].push_back(edge.first);
        }
    }
        
    vector<vector<int>> d(n, vector<int> (n, 0));
    
    for(int i = 0; i < n; ++i) {
        int now = 0;
        dfs(i, -1, G, C, d[i], now);
    }

    int q; cin >> q;
    for(int i = 0; i < q; ++i) {
        int x, y; cin >> x >> y;
        x--;y--;
        cout << ans - d[x][y] << "\n";
    }
}
```