// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 4005 , M = 4e5 + 10;
int n , m , cost[N][N] , a[M] , b[M] , c[M] , id[M];
int Q;
int fa[N];
vi contain[N];
int F(int x) {return fa[x] == x ? x : fa[x] = F(fa[x]);}

int main(){
  scanf("%d%d",&n,&m);
  rep(i,0,m) scanf("%d%d%d",a+i,b+i,c+i),id[i]=i;
  rep(i,1,n+1) fa[i]=i,contain[i].pb(i);
  sort(id,id+m,[&](int x,int y){return c[x]<c[y];});
  ll sum = 0;
  rep(i,0,m) {
    int u=F(a[id[i]]) , v=F(b[id[i]]);
    if(u != v) {
      sum += c[id[i]];
      if(sz(contain[u]) < sz(contain[v]))
        swap(u , v);
      for(auto e : contain[u])
        for(auto f : contain[v])
          cost[e][f] = cost[f][e] = c[id[i]];
      contain[u].insert(contain[u].end(),all(contain[v]));
      contain[v].clear();
      fa[v] = u;
    }
  }
  scanf("%d",&Q);
  rep(i,0,Q) {
    int s,t;
    scanf("%d%d",&s,&t);
    printf("%lld\n",sum-cost[s][t]);
  }
  return 0;
}

### Prompt

Generate 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 {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 4005 , M = 4e5 + 10;
int n , m , cost[N][N] , a[M] , b[M] , c[M] , id[M];
int Q;
int fa[N];
vi contain[N];
int F(int x) {return fa[x] == x ? x : fa[x] = F(fa[x]);}

int main(){
  scanf("%d%d",&n,&m);
  rep(i,0,m) scanf("%d%d%d",a+i,b+i,c+i),id[i]=i;
  rep(i,1,n+1) fa[i]=i,contain[i].pb(i);
  sort(id,id+m,[&](int x,int y){return c[x]<c[y];});
  ll sum = 0;
  rep(i,0,m) {
    int u=F(a[id[i]]) , v=F(b[id[i]]);
    if(u != v) {
      sum += c[id[i]];
      if(sz(contain[u]) < sz(contain[v]))
        swap(u , v);
      for(auto e : contain[u])
        for(auto f : contain[v])
          cost[e][f] = cost[f][e] = c[id[i]];
      contain[u].insert(contain[u].end(),all(contain[v]));
      contain[v].clear();
      fa[v] = u;
    }
  }
  scanf("%d",&Q);
  rep(i,0,Q) {
    int s,t;
    scanf("%d%d",&s,&t);
    printf("%lld\n",sum-cost[s][t]);
  }
  return 0;
}

```