#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;

struct uni {
  vector<int> p;
  uni(int n) :
      p(n, -1) {}
  int root(int a) {
    return p[a] < 0 ? a : (p[a] = root(p[a]));
  }
  bool find(int a, int b) {
    return root(a) == root(b);
  }
  bool merge(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return false;
    p[a] = b;
    return true;
  }
};

struct edge {
  int f, t, c;
  edge() {}
  edge(int f, int t, int c) :
      f(f), t(t), c(c) {}
  bool operator<(const edge& e) const {
    return c < e.c;
  }
};

edge e[444444];
vector<edge> g[4444];
int res[4444][4444];

void solve(int f, int v, int p, int c) {
  res[f][v] = c;
  for (int i = 0; i < int(g[v].size()); i++) {
    if (g[v][i].t == p) continue;
    solve(f, g[v][i].t, v, max(c, g[v][i].c));
  }
}

int main(void) {
  scanf("%d%d", &n, &m);
  uni u(n);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &e[i].f, &e[i].t, &e[i].c);
    --e[i].f;
    --e[i].t;
  }
  sort(e, e+m);
  long long c = 0;
  for (int i = 0; i < m; i++) {
    if (u.merge(e[i].f, e[i].t)) {
      c += e[i].c;
      g[e[i].f].push_back(edge(e[i].f, e[i].t, e[i].c));
      g[e[i].t].push_back(edge(e[i].t, e[i].f, e[i].c));
    }
  }
  for (int i = 0; i < n; i++) {
    solve(i, i, -1, 0);
  }
  int q; scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int s, t; scanf("%d%d", &s, &t); --s; --t;
    printf("%lld\n", c-res[s][t]);
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;

struct uni {
  vector<int> p;
  uni(int n) :
      p(n, -1) {}
  int root(int a) {
    return p[a] < 0 ? a : (p[a] = root(p[a]));
  }
  bool find(int a, int b) {
    return root(a) == root(b);
  }
  bool merge(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return false;
    p[a] = b;
    return true;
  }
};

struct edge {
  int f, t, c;
  edge() {}
  edge(int f, int t, int c) :
      f(f), t(t), c(c) {}
  bool operator<(const edge& e) const {
    return c < e.c;
  }
};

edge e[444444];
vector<edge> g[4444];
int res[4444][4444];

void solve(int f, int v, int p, int c) {
  res[f][v] = c;
  for (int i = 0; i < int(g[v].size()); i++) {
    if (g[v][i].t == p) continue;
    solve(f, g[v][i].t, v, max(c, g[v][i].c));
  }
}

int main(void) {
  scanf("%d%d", &n, &m);
  uni u(n);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &e[i].f, &e[i].t, &e[i].c);
    --e[i].f;
    --e[i].t;
  }
  sort(e, e+m);
  long long c = 0;
  for (int i = 0; i < m; i++) {
    if (u.merge(e[i].f, e[i].t)) {
      c += e[i].c;
      g[e[i].f].push_back(edge(e[i].f, e[i].t, e[i].c));
      g[e[i].t].push_back(edge(e[i].t, e[i].f, e[i].c));
    }
  }
  for (int i = 0; i < n; i++) {
    solve(i, i, -1, 0);
  }
  int q; scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int s, t; scanf("%d%d", &s, &t); --s; --t;
    printf("%lld\n", c-res[s][t]);
  }
  return 0;
}

```