#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> cld;
class disjoint_set {
  public:
    int cnt;
    vector<int> rank, prt, now, lg;
    disjoint_set(int size) {
      cnt = size;
      rank.resize(size);
      prt.resize(size);
      now.resize(size);
      lg.resize(2 * size - 1);
      lg.resize(2 * size - 1);
      for (int i = 0; i < size; i++) {
        prt[i] = i;
        rank[i] = 0;
        now[i] = i;
      }
    }
  int find (int x) {
    if (x == prt[x]) return x;
    return prt[x] = find(prt[x]);
  }
  bool is_equiv (int x, int y) {
    return find(x) == find(y);
  }
  int unite (int x, int y) {
    x = find(x);
    y = find(y);
    lg[now[x]] = lg[now[y]] = cnt;
    cld[cnt].push_back(now[x]);
    cld[cnt].push_back(now[y]);
    now[x] = now[y] = cnt;
    if (x == y) return false;
    if (rank[x] > rank[y]) swap(x, y);
    prt[x] = y;
    if (rank[x] == rank[y]) rank[y]++;
    return cnt++;
  }
};
vector<int> dpt;
void dfs (int crr, int d) {
  dpt[crr] = d;
  for (int nxt : cld[crr]) {
    dfs(nxt, d + 1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int, pair<int, int>>> grh(m);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    grh[i] = {c, {--a, --b}};
  }
  sort(grh.begin(), grh.end());
  int N = 2 * n - 1;
  cld.resize(N);
  vector<int> cut(N);
  disjoint_set djs(n);
  long long sum = 0;
  int cnt = 0;
  for (auto e : grh) {
    int c = e.first;
    int a = e.second.first;
    int b = e.second.second;
    if (!djs.is_equiv(a, b)) {
      cut[djs.unite(a, b)] = c;
      sum += c;
      cnt++;
    }
  }
  const int PMAX = 20;
  vector<vector<int>> asc(PMAX, vector<int>(N));
  for (int i = 0; i < N; i++) {
    asc[0][i] = djs.lg[i];
  }
  asc[0][N - 1] = N - 1;
  for (int p = 1; p < PMAX; p++) {
    for (int i = 0; i < N; i++) {
      asc[p][i] = asc[p - 1][asc[p - 1][i]];
    }
  }
  dpt.resize(N);
  dfs(N - 1, 0);
  int q;
  cin >> q;
  while (q--) {
    int s, t;
    cin >> s >> t;
    if (dpt[--s] > dpt[--t]) swap(s, t);
    int d = dpt[t] - dpt[s];
    for (int p = 0; p < PMAX; p++){
      if (d & 1) {
        t = asc[p][t];
      }
      d >>= 1;
      if (d == 0) break;
    }
    long long ret = sum;
    for (int p = PMAX - 1; p >= 0; p--) {
      if (asc[p][s] != asc[p][t]) {
        s = asc[p][s];
        t = asc[p][t];
      }
    }
    if (s != t) {
      s = asc[0][s];
      t = asc[0][t];
    }
    ret -= cut[s];
    cout << ret << '\n';
  }
  return 0;
}
### Prompt

Your challenge is to write 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;
vector<vector<int>> cld;
class disjoint_set {
  public:
    int cnt;
    vector<int> rank, prt, now, lg;
    disjoint_set(int size) {
      cnt = size;
      rank.resize(size);
      prt.resize(size);
      now.resize(size);
      lg.resize(2 * size - 1);
      lg.resize(2 * size - 1);
      for (int i = 0; i < size; i++) {
        prt[i] = i;
        rank[i] = 0;
        now[i] = i;
      }
    }
  int find (int x) {
    if (x == prt[x]) return x;
    return prt[x] = find(prt[x]);
  }
  bool is_equiv (int x, int y) {
    return find(x) == find(y);
  }
  int unite (int x, int y) {
    x = find(x);
    y = find(y);
    lg[now[x]] = lg[now[y]] = cnt;
    cld[cnt].push_back(now[x]);
    cld[cnt].push_back(now[y]);
    now[x] = now[y] = cnt;
    if (x == y) return false;
    if (rank[x] > rank[y]) swap(x, y);
    prt[x] = y;
    if (rank[x] == rank[y]) rank[y]++;
    return cnt++;
  }
};
vector<int> dpt;
void dfs (int crr, int d) {
  dpt[crr] = d;
  for (int nxt : cld[crr]) {
    dfs(nxt, d + 1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int, pair<int, int>>> grh(m);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    grh[i] = {c, {--a, --b}};
  }
  sort(grh.begin(), grh.end());
  int N = 2 * n - 1;
  cld.resize(N);
  vector<int> cut(N);
  disjoint_set djs(n);
  long long sum = 0;
  int cnt = 0;
  for (auto e : grh) {
    int c = e.first;
    int a = e.second.first;
    int b = e.second.second;
    if (!djs.is_equiv(a, b)) {
      cut[djs.unite(a, b)] = c;
      sum += c;
      cnt++;
    }
  }
  const int PMAX = 20;
  vector<vector<int>> asc(PMAX, vector<int>(N));
  for (int i = 0; i < N; i++) {
    asc[0][i] = djs.lg[i];
  }
  asc[0][N - 1] = N - 1;
  for (int p = 1; p < PMAX; p++) {
    for (int i = 0; i < N; i++) {
      asc[p][i] = asc[p - 1][asc[p - 1][i]];
    }
  }
  dpt.resize(N);
  dfs(N - 1, 0);
  int q;
  cin >> q;
  while (q--) {
    int s, t;
    cin >> s >> t;
    if (dpt[--s] > dpt[--t]) swap(s, t);
    int d = dpt[t] - dpt[s];
    for (int p = 0; p < PMAX; p++){
      if (d & 1) {
        t = asc[p][t];
      }
      d >>= 1;
      if (d == 0) break;
    }
    long long ret = sum;
    for (int p = PMAX - 1; p >= 0; p--) {
      if (asc[p][s] != asc[p][t]) {
        s = asc[p][s];
        t = asc[p][t];
      }
    }
    if (s != t) {
      s = asc[0][s];
      t = asc[0][t];
    }
    ret -= cut[s];
    cout << ret << '\n';
  }
  return 0;
}
```