#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

class union_find {
private:
  unordered_map<lli,lli> par;
  unordered_map<lli,lli> rnk;
public:
  // union_find (lli n){
  //   par = new vll(n);
  //   iota(par->begin(),par->end(),0);
  //   rnk = new vll(n,0);
  // }
  lli parent(lli x){
    if(par[x]) return par[x];
    else return par[x] = x;
  }
  lli find(lli x){
    if(parent(x) == x) return x;
    else return par[x] = find(parent(x));
  }
  void unite(lli x,lli y){
    x = find(x);y = find(y);
    if(x == y)return;
    if(rnk[x] < rnk[y]) par[x] = y;
    else {
      par[y] = x;
      if(rnk[x] == rnk[y]) rnk[x]++;
    }
  }
  bool same(lli x,lli y){
    return find(x) == find(y);
  }
};

lli n,m;
graph g;
graph t;
lli q;
union_find uf;
mat edge;
mat ans;
lli mst = 0;

void dfs(lli x, lli c, lli p, lli from){
  ans[from][x] = c;
  for(auto y : t[x]){
    if(y.first == p) continue;
    dfs(y.first, max(y.second, c), x, from);
  }
}


int main(){
  cin >> n >> m;
  edge = mat(m, vll(3));
  for(lli i=0;i < m;i++){
    cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
  }
  sort(edge.begin(), edge.end());
  for(lli i = 0;i < m;i++){
    if(uf.same(edge[i][1], edge[i][2])) continue;
    uf.unite(edge[i][1], edge[i][2]);
    t[edge[i][1]][edge[i][2]] = t[edge[i][2]][edge[i][1]] = edge[i][0];
    mst += edge[i][0];
  }
  ans = mat(n+1,vll(n+1));
  for(lli i = 1;i <= n;i++){
    dfs(i, 0, 0, i);
  }
  cin >> q;
  for(lli i = 0;i <  q;i++){
    lli s,t;
    cin >> s >> t;
    cout << mst-ans[s][t] << endl;
  }
  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 <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

class union_find {
private:
  unordered_map<lli,lli> par;
  unordered_map<lli,lli> rnk;
public:
  // union_find (lli n){
  //   par = new vll(n);
  //   iota(par->begin(),par->end(),0);
  //   rnk = new vll(n,0);
  // }
  lli parent(lli x){
    if(par[x]) return par[x];
    else return par[x] = x;
  }
  lli find(lli x){
    if(parent(x) == x) return x;
    else return par[x] = find(parent(x));
  }
  void unite(lli x,lli y){
    x = find(x);y = find(y);
    if(x == y)return;
    if(rnk[x] < rnk[y]) par[x] = y;
    else {
      par[y] = x;
      if(rnk[x] == rnk[y]) rnk[x]++;
    }
  }
  bool same(lli x,lli y){
    return find(x) == find(y);
  }
};

lli n,m;
graph g;
graph t;
lli q;
union_find uf;
mat edge;
mat ans;
lli mst = 0;

void dfs(lli x, lli c, lli p, lli from){
  ans[from][x] = c;
  for(auto y : t[x]){
    if(y.first == p) continue;
    dfs(y.first, max(y.second, c), x, from);
  }
}


int main(){
  cin >> n >> m;
  edge = mat(m, vll(3));
  for(lli i=0;i < m;i++){
    cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
  }
  sort(edge.begin(), edge.end());
  for(lli i = 0;i < m;i++){
    if(uf.same(edge[i][1], edge[i][2])) continue;
    uf.unite(edge[i][1], edge[i][2]);
    t[edge[i][1]][edge[i][2]] = t[edge[i][2]][edge[i][1]] = edge[i][0];
    mst += edge[i][0];
  }
  ans = mat(n+1,vll(n+1));
  for(lli i = 1;i <= n;i++){
    dfs(i, 0, 0, i);
  }
  cin >> q;
  for(lli i = 0;i <  q;i++){
    lli s,t;
    cin >> s >> t;
    cout << mst-ans[s][t] << endl;
  }
  return 0;
}

```