/**
 *    author:  tourist
 *    created: 26.11.2019 09:10:09       
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> e(m);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x; --y;
    e[i] = make_tuple(z, x, y);
  }
  sort(e.begin(), e.end());
  long long ans = 0;
  vector<int> fi(n);
  iota(fi.begin(), fi.end(), 0);
  vector<int> ne(n, -1);
  vector<int> nc(n, -1);
  dsu d(n);
  for (auto& ee : e) {
    int x = get<1>(ee);
    int y = get<2>(ee);
    int z = get<0>(ee);
    x = d.get(x);
    y = d.get(y);
    if (x != y) {
      d.p[x] = y;
      ne[x] = fi[y];
      nc[x] = z;
      fi[y] = fi[x];
      ans += z;
    }
  }
  int start = fi[d.get(0)];
  vector<int> order(n);
  vector<int> val(n - 1);
  vector<int> pos(n);
  for (int i = 0; i < n; i++) {
    if (i < n - 1) {
      val[i] = nc[start];
    }
    order[i] = start;
    pos[start] = i;
    start = ne[start];
  }
  SparseTable<int> st(val, [&](int i, int j) { return max(i, j); });
  int tt;
  cin >> tt;
  while (tt--) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    x = pos[x];
    y = pos[y];
    if (x > y) {
      swap(x, y);
    }
    cout << ans - st.get(x, y - 1) << '\n';
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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
/**
 *    author:  tourist
 *    created: 26.11.2019 09:10:09       
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> e(m);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x; --y;
    e[i] = make_tuple(z, x, y);
  }
  sort(e.begin(), e.end());
  long long ans = 0;
  vector<int> fi(n);
  iota(fi.begin(), fi.end(), 0);
  vector<int> ne(n, -1);
  vector<int> nc(n, -1);
  dsu d(n);
  for (auto& ee : e) {
    int x = get<1>(ee);
    int y = get<2>(ee);
    int z = get<0>(ee);
    x = d.get(x);
    y = d.get(y);
    if (x != y) {
      d.p[x] = y;
      ne[x] = fi[y];
      nc[x] = z;
      fi[y] = fi[x];
      ans += z;
    }
  }
  int start = fi[d.get(0)];
  vector<int> order(n);
  vector<int> val(n - 1);
  vector<int> pos(n);
  for (int i = 0; i < n; i++) {
    if (i < n - 1) {
      val[i] = nc[start];
    }
    order[i] = start;
    pos[start] = i;
    start = ne[start];
  }
  SparseTable<int> st(val, [&](int i, int j) { return max(i, j); });
  int tt;
  cin >> tt;
  while (tt--) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    x = pos[x];
    y = pos[y];
    if (x > y) {
      swap(x, y);
    }
    cout << ans - st.get(x, y - 1) << '\n';
  }
  return 0;
}

```