#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

struct edge{
    int from, to, cost;
    bool operator<(const edge &another) const
    {
        return cost < another.cost;
    };
};

//vector<edge> G[4000];
vector<edge> MST[4000];
vector<edge> es;
bool used[4000];
int max_edge[4000][4000];

int N, M;

void clear_used(){
    for(int i = 0; i < N; i++) used[i] = false;
}

void dfs(int root, int cur, int max_e){
    used[cur] = true;
    max_edge[root][cur] = max_e;
    for(int i = 0; i < MST[cur].size(); i++){
        if(!used[MST[cur][i].to]){
            dfs(root, MST[cur][i].to, max(max_e, MST[cur][i].cost));
        }
    }
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < M ; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        es.push_back(edge{a, b, c});
    }
    UnionFind uf(N);
    sort(es.begin(), es.end());
    long sum = 0;
    for(int i = 0; i < M; i++){
        int from = es[i].from;
        int to = es[i].to;
        int cost = es[i].cost;
        if(uf.root(from) != uf.root(to)){
            //cout << "MST" << endl;
            MST[from].push_back(es[i]);
            MST[to].push_back((edge){to, from, cost});
            uf.unionSet(from, to);
            sum += (long)cost;
        }
    }
    for(int i = 0; i < N; i++){
        clear_used();
        dfs(i, i, 0);
    }
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        //cout << max_edge[s][t] << endl;
        cout << sum-max_edge[s][t] << endl;
    }
}


### Prompt

Please create a solution in cpp 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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

struct edge{
    int from, to, cost;
    bool operator<(const edge &another) const
    {
        return cost < another.cost;
    };
};

//vector<edge> G[4000];
vector<edge> MST[4000];
vector<edge> es;
bool used[4000];
int max_edge[4000][4000];

int N, M;

void clear_used(){
    for(int i = 0; i < N; i++) used[i] = false;
}

void dfs(int root, int cur, int max_e){
    used[cur] = true;
    max_edge[root][cur] = max_e;
    for(int i = 0; i < MST[cur].size(); i++){
        if(!used[MST[cur][i].to]){
            dfs(root, MST[cur][i].to, max(max_e, MST[cur][i].cost));
        }
    }
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < M ; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        es.push_back(edge{a, b, c});
    }
    UnionFind uf(N);
    sort(es.begin(), es.end());
    long sum = 0;
    for(int i = 0; i < M; i++){
        int from = es[i].from;
        int to = es[i].to;
        int cost = es[i].cost;
        if(uf.root(from) != uf.root(to)){
            //cout << "MST" << endl;
            MST[from].push_back(es[i]);
            MST[to].push_back((edge){to, from, cost});
            uf.unionSet(from, to);
            sum += (long)cost;
        }
    }
    for(int i = 0; i < N; i++){
        clear_used();
        dfs(i, i, 0);
    }
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        //cout << max_edge[s][t] << endl;
        cout << sum-max_edge[s][t] << endl;
    }
}


```