#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

class U {
public:
  int n;
  vector<int> p, s;

  U(int _) {
    n = _;
    p.resize(n);
    s.resize(n);
    for (int i = 0; i < n; i++) {
      p[i] = i;
      s[i] = 1;
    }
  }

  bool connect(int a, int b) {
    int ap, bp;
    for (ap = p[a]; ap != p[ap]; ap = p[ap]);
    for (bp = p[b]; bp != p[bp]; bp = p[bp]);
    if (ap == bp)
      return true;
    int mi = min(ap, bp), ma = max(ap, bp);
    p[ma] = mi;
    s[mi] += s[ma];
    s[ma] = 0;
    for (int pp = a; pp != mi;) {
      int next = p[pp];
      p[pp] = mi;
      pp = next;
    }
    for (int pp = b; pp != mi;) {
      int next = p[pp];
      p[pp] = mi;
      pp = next;
    }
    return false;
  }

  int q(int a) {
    int ap;
    for (ap = a; ap != p[ap]; ap = p[ap]);
    return s[ap];
  }

  int parent(int a) {
    int ap;
    for (ap = a; ap != p[ap]; ap = p[ap]);
    return p[ap];
  }

  bool query(int a, int b) { return parent(a) == parent(b); }
};

vector<vector<pair<int, ll>>> ps;

void dfs(vector<vector<ll>> &dist, int i, int from, int base, ll maxp) {
  dist[base][i] = maxp;
  for (auto &v : ps[i]) {
    if (v.first == from) continue;
    dfs(dist, v.first, i, base, max(v.second, maxp));
  }
}

struct N {
  int a, b;
  ll c;
};

bool operator<(const N &l, const N &r) {
  return l.c < r.c;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  ps.resize(n);
  U u(n);
  ll sum = 0;
  vector<N> ns(m);
  for (int i = 0; i < m; i++) {
    cin >> ns[i].a >> ns[i].b >> ns[i].c;
    ns[i].a--;
    ns[i].b--;
  }
  sort(ns.begin(), ns.end());
  for (int i = 0; i < m; i++) {
    if (!u.connect(ns[i].a, ns[i].b)) {
      ps[ns[i].a].emplace_back(ns[i].b, ns[i].c);
      ps[ns[i].b].emplace_back(ns[i].a, ns[i].c);
      sum += ns[i].c;
    }
  }
  vector<vector<ll>> dist(n, vector<ll>(n, -1));

  for (int i = 0; i < n; i++) {
    dfs(dist, i, -1, i, 0);
  }

  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int s, t;
    cin >> s >> t;
    s--;
    t--;
    cout << sum - dist[s][t] << endl;
  }

  return 0;
}

### 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 <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

class U {
public:
  int n;
  vector<int> p, s;

  U(int _) {
    n = _;
    p.resize(n);
    s.resize(n);
    for (int i = 0; i < n; i++) {
      p[i] = i;
      s[i] = 1;
    }
  }

  bool connect(int a, int b) {
    int ap, bp;
    for (ap = p[a]; ap != p[ap]; ap = p[ap]);
    for (bp = p[b]; bp != p[bp]; bp = p[bp]);
    if (ap == bp)
      return true;
    int mi = min(ap, bp), ma = max(ap, bp);
    p[ma] = mi;
    s[mi] += s[ma];
    s[ma] = 0;
    for (int pp = a; pp != mi;) {
      int next = p[pp];
      p[pp] = mi;
      pp = next;
    }
    for (int pp = b; pp != mi;) {
      int next = p[pp];
      p[pp] = mi;
      pp = next;
    }
    return false;
  }

  int q(int a) {
    int ap;
    for (ap = a; ap != p[ap]; ap = p[ap]);
    return s[ap];
  }

  int parent(int a) {
    int ap;
    for (ap = a; ap != p[ap]; ap = p[ap]);
    return p[ap];
  }

  bool query(int a, int b) { return parent(a) == parent(b); }
};

vector<vector<pair<int, ll>>> ps;

void dfs(vector<vector<ll>> &dist, int i, int from, int base, ll maxp) {
  dist[base][i] = maxp;
  for (auto &v : ps[i]) {
    if (v.first == from) continue;
    dfs(dist, v.first, i, base, max(v.second, maxp));
  }
}

struct N {
  int a, b;
  ll c;
};

bool operator<(const N &l, const N &r) {
  return l.c < r.c;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  ps.resize(n);
  U u(n);
  ll sum = 0;
  vector<N> ns(m);
  for (int i = 0; i < m; i++) {
    cin >> ns[i].a >> ns[i].b >> ns[i].c;
    ns[i].a--;
    ns[i].b--;
  }
  sort(ns.begin(), ns.end());
  for (int i = 0; i < m; i++) {
    if (!u.connect(ns[i].a, ns[i].b)) {
      ps[ns[i].a].emplace_back(ns[i].b, ns[i].c);
      ps[ns[i].b].emplace_back(ns[i].a, ns[i].c);
      sum += ns[i].c;
    }
  }
  vector<vector<ll>> dist(n, vector<ll>(n, -1));

  for (int i = 0; i < n; i++) {
    dfs(dist, i, -1, i, 0);
  }

  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int s, t;
    cin >> s >> t;
    s--;
    t--;
    cout << sum - dist[s][t] << endl;
  }

  return 0;
}

```