#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 2e9;
const ld EPS = 1e-8;

typedef ll Weight;
typedef int Flow;

struct Edge {
  int src, dest, rev;
  Flow cap;
  Weight cost;
  bool operator < (const Edge &rhs) const {
    return cost > rhs.cost;
  }
  Edge(int s, int d) : src(s), dest(d) { ; }
  Edge(int s, int d, int c) : src(s), dest(d), cost(c) { ; }
  Edge(int s, int d, int r, Flow cp, Weight cst) : src(s), dest(d), rev(r), cap(cp), cost(cst) { ; }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

bool comp(const Edge &e1, const Edge &e2){
  return e1.cost < e2.cost;
}

pair<Weight, Edges> kruskal(Edges &es, int v){
  sort(ALL(es), comp);
  UnionFind uni(v);
  Edges mst;
  Weight res = 0;
  for(Edge e: es){
    if(!uni.findSet(e.src, e.dest)){
      uni.unionSet(e.src, e.dest);
      mst.push_back(e);
      res += e.cost;
    }
  }
  return make_pair(res, mst);
}

int main(){
  int N, M;
  cin >> N >> M;
  Edges es;
  REP(i,M) {
    int a, b, c;
    cin >> a >> b >> c; --a; --b;
    es.push_back(Edge(a, b, c));
    es.push_back(Edge(b, a, c));
  }

  pair<Weight, Edges> mst = kruskal(es, N);
  Graph g(N);
  for(Edge e: mst.second) {
    g[e.src].push_back(e);
    g[e.dest].push_back(Edge(e.dest, e.src, e.cost));
  }
  /*
  REP(i,N) {
    for(Edge e: g[i]) {
      cout << e.dest << " ";
    }
    cout << endl;
  }
  */

  vector<vector<int>> d(N, vector<int> (N, 0));
  REP(i,N) {
    queue<tuple<int,int,ll>> que;
    que.push(make_tuple(i, -1, 0));
    while(!que.empty()) {
      int curr, prev, cst;
      tie(curr, prev, cst) = que.front(); que.pop();
      d[i][curr] = max(d[i][curr], cst);
      for(Edge e: g[curr]) {
        if(e.dest == prev) continue;
        que.push(make_tuple(e.dest, curr, max((ll)cst, e.cost)));
      }
    }
  }
  /*
  REP(i,N){
    REP(j,N) cout << " " << d[i][j];
    cout << endl;
  }
  */

  int Q;
  cin >> Q;
  REP(q, Q) {
    int S, T;
    cin >> S >> T; --S; --T;
    ll res = mst.first - d[S][T];
    cout << res << endl;
  }
  return 0;
}


### Prompt

Create a solution in cpp for 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;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 2e9;
const ld EPS = 1e-8;

typedef ll Weight;
typedef int Flow;

struct Edge {
  int src, dest, rev;
  Flow cap;
  Weight cost;
  bool operator < (const Edge &rhs) const {
    return cost > rhs.cost;
  }
  Edge(int s, int d) : src(s), dest(d) { ; }
  Edge(int s, int d, int c) : src(s), dest(d), cost(c) { ; }
  Edge(int s, int d, int r, Flow cp, Weight cst) : src(s), dest(d), rev(r), cap(cp), cost(cst) { ; }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

bool comp(const Edge &e1, const Edge &e2){
  return e1.cost < e2.cost;
}

pair<Weight, Edges> kruskal(Edges &es, int v){
  sort(ALL(es), comp);
  UnionFind uni(v);
  Edges mst;
  Weight res = 0;
  for(Edge e: es){
    if(!uni.findSet(e.src, e.dest)){
      uni.unionSet(e.src, e.dest);
      mst.push_back(e);
      res += e.cost;
    }
  }
  return make_pair(res, mst);
}

int main(){
  int N, M;
  cin >> N >> M;
  Edges es;
  REP(i,M) {
    int a, b, c;
    cin >> a >> b >> c; --a; --b;
    es.push_back(Edge(a, b, c));
    es.push_back(Edge(b, a, c));
  }

  pair<Weight, Edges> mst = kruskal(es, N);
  Graph g(N);
  for(Edge e: mst.second) {
    g[e.src].push_back(e);
    g[e.dest].push_back(Edge(e.dest, e.src, e.cost));
  }
  /*
  REP(i,N) {
    for(Edge e: g[i]) {
      cout << e.dest << " ";
    }
    cout << endl;
  }
  */

  vector<vector<int>> d(N, vector<int> (N, 0));
  REP(i,N) {
    queue<tuple<int,int,ll>> que;
    que.push(make_tuple(i, -1, 0));
    while(!que.empty()) {
      int curr, prev, cst;
      tie(curr, prev, cst) = que.front(); que.pop();
      d[i][curr] = max(d[i][curr], cst);
      for(Edge e: g[curr]) {
        if(e.dest == prev) continue;
        que.push(make_tuple(e.dest, curr, max((ll)cst, e.cost)));
      }
    }
  }
  /*
  REP(i,N){
    REP(j,N) cout << " " << d[i][j];
    cout << endl;
  }
  */

  int Q;
  cin >> Q;
  REP(q, Q) {
    int S, T;
    cin >> S >> T; --S; --T;
    ll res = mst.first - d[S][T];
    cout << res << endl;
  }
  return 0;
}


```