#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

struct UnionFind {
  vector<int> c, s;
  UnionFind(size_t n) : c(n), s(n, 1) { iota(begin(c), end(c), 0); }
  int root(int i) { return c[i] == i ? i : (c[i] = root(c[i])); }
  bool same(int i, int j) { return root(i) == root(j); }
  void unite(int i, int j) {
    i = root(i); j = root(j);
    if (i != j) {
      if (s[i] > s[j]) { c[j] = i; s[i] += s[j]; }
      else { c[i] = j; s[j] += s[i]; }
    }
  }
  int size(int i) { return s[root(i)]; }
};

i64 n, m;
using P = pair<i64, i64>;
vector<vector<P>> g;
vector<vector<i64>> mw;

void dfs(i64 r, i64 u, i64 b) {
  for (auto p : g[u]) {
    i64 v, c;
    tie(v, c) = p;
    if (v == b) continue;
    mw[r][v] = max(mw[r][u], c);
    dfs(r, v, u);
  }
}

int main() {
  cin >> n >> m;
  vector<tuple<i64, i64, i64>> es, tes;
  for (i64 i = 0; i < m; ++i) {
    i64 a, b, c;
    cin >> a >> b >> c;
    es.emplace_back(c, a, b);
  }
  sort(begin(es), end(es));
  UnionFind uf(n + 1);
  i64 csum = 0;
  for (i64 i = 0; tes.size() < n - 1; ++i) {
    auto t = es[i];
    i64 a, b, c;
    tie(c, a, b) = t;
    if (!uf.same(a, b)) {
      tes.emplace_back(c, a, b);
      csum += c;
      uf.unite(a, b);
    }
  }
  
  init_n(g, n + 1);
  for (auto e : tes) {
    i64 a, b, c;
    tie(c, a, b) = e;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }

  init_n(mw, n + 1, vector<i64>(n + 1));
  for (i64 r = 1; r <= n; ++r) {
    dfs(r, r, 0);
  }

  i64 q;
  cin >> q;
  while (q--) {
    i64 s, t;
    cin >> s >> t;
    cout << csum - mw[s][t] << '\n';
  }
  return 0;
}

### 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 <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

struct UnionFind {
  vector<int> c, s;
  UnionFind(size_t n) : c(n), s(n, 1) { iota(begin(c), end(c), 0); }
  int root(int i) { return c[i] == i ? i : (c[i] = root(c[i])); }
  bool same(int i, int j) { return root(i) == root(j); }
  void unite(int i, int j) {
    i = root(i); j = root(j);
    if (i != j) {
      if (s[i] > s[j]) { c[j] = i; s[i] += s[j]; }
      else { c[i] = j; s[j] += s[i]; }
    }
  }
  int size(int i) { return s[root(i)]; }
};

i64 n, m;
using P = pair<i64, i64>;
vector<vector<P>> g;
vector<vector<i64>> mw;

void dfs(i64 r, i64 u, i64 b) {
  for (auto p : g[u]) {
    i64 v, c;
    tie(v, c) = p;
    if (v == b) continue;
    mw[r][v] = max(mw[r][u], c);
    dfs(r, v, u);
  }
}

int main() {
  cin >> n >> m;
  vector<tuple<i64, i64, i64>> es, tes;
  for (i64 i = 0; i < m; ++i) {
    i64 a, b, c;
    cin >> a >> b >> c;
    es.emplace_back(c, a, b);
  }
  sort(begin(es), end(es));
  UnionFind uf(n + 1);
  i64 csum = 0;
  for (i64 i = 0; tes.size() < n - 1; ++i) {
    auto t = es[i];
    i64 a, b, c;
    tie(c, a, b) = t;
    if (!uf.same(a, b)) {
      tes.emplace_back(c, a, b);
      csum += c;
      uf.unite(a, b);
    }
  }
  
  init_n(g, n + 1);
  for (auto e : tes) {
    i64 a, b, c;
    tie(c, a, b) = e;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }

  init_n(mw, n + 1, vector<i64>(n + 1));
  for (i64 r = 1; r <= n; ++r) {
    dfs(r, r, 0);
  }

  i64 q;
  cin >> q;
  while (q--) {
    i64 s, t;
    cin >> s >> t;
    cout << csum - mw[s][t] << '\n';
  }
  return 0;
}

```