#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define len(val) static_cast<ll>(val.size())
#define rep(i, n) for(ll i=0; i<(n); i++)

const ll MAXN = 4000;
const ll MAXM = 400000;
const ll INF = 1e18;
ll N, M;

struct UnionFind
{
    std::vector<ll> data;
    UnionFind(ll size) : data(size, -1){}
    void initialize(void){
        for(ll i=0; i<(ll)data.size(); i++) data[i] = i;
    }
    bool merge(ll x, ll y){
        x = find(x); y = find(y);
        if(x == y) return false;
        else{ data[x] = y; return true; }
    }
    ll find(ll x){ //根っこを見つける関数
        if(data[x] == x) return x;
        else return data[x] = find(data[x]); //経路圧縮
    }
    bool isSame(ll x, ll y){
        return find(x) == find(y);
    }
};

struct edge{
  ll u, v, cost;
};

bool comp(const edge& r, const edge& l){
  return r.cost < l.cost;
}

edge es[MAXM];
ll mx[MAXN][MAXN];
bool visited[MAXN];
vector<P> G[MAXN];

void dfs(ll v, ll p, ll m = -1)
{
  if(visited[v]) return;
  mx[p][v] = m;
  visited[v] = true;
  for(auto a : G[v]){
    dfs(a.first, p, max(m, a.second));
  }
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> M;
  rep(i, M){
    ll a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    es[i] = edge{a, b, c};
  }
  ll sum = 0;
  {
    sort(es, es+M, comp);
    UnionFind uf(N);
    uf.initialize();
    ll cnt = 0;
    rep(i, M){
      edge& e = es[i];
      if(!uf.isSame(e.u, e.v)){
        uf.merge(e.u, e.v);
        es[cnt] = edge{e.u, e.v, e.cost};
        cnt++;
        sum += e.cost;
        G[e.u].push_back(make_pair(e.v, e.cost));
        G[e.v].push_back(make_pair(e.u, e.cost));
      }
    }
  }
  for(int i=0; i<N; i++){
    memset(visited, false, sizeof(visited));
    dfs(i, i);
  }

  ll Q;
  cin >> Q;
  rep(q, Q){
    ll s, t;
    cin >> s >> t;
    s--; t--;
    cout << sum-mx[s][t] << endl;
  }
}

### 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;
typedef long long ll;
typedef pair<ll, ll> P;
#define len(val) static_cast<ll>(val.size())
#define rep(i, n) for(ll i=0; i<(n); i++)

const ll MAXN = 4000;
const ll MAXM = 400000;
const ll INF = 1e18;
ll N, M;

struct UnionFind
{
    std::vector<ll> data;
    UnionFind(ll size) : data(size, -1){}
    void initialize(void){
        for(ll i=0; i<(ll)data.size(); i++) data[i] = i;
    }
    bool merge(ll x, ll y){
        x = find(x); y = find(y);
        if(x == y) return false;
        else{ data[x] = y; return true; }
    }
    ll find(ll x){ //根っこを見つける関数
        if(data[x] == x) return x;
        else return data[x] = find(data[x]); //経路圧縮
    }
    bool isSame(ll x, ll y){
        return find(x) == find(y);
    }
};

struct edge{
  ll u, v, cost;
};

bool comp(const edge& r, const edge& l){
  return r.cost < l.cost;
}

edge es[MAXM];
ll mx[MAXN][MAXN];
bool visited[MAXN];
vector<P> G[MAXN];

void dfs(ll v, ll p, ll m = -1)
{
  if(visited[v]) return;
  mx[p][v] = m;
  visited[v] = true;
  for(auto a : G[v]){
    dfs(a.first, p, max(m, a.second));
  }
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> M;
  rep(i, M){
    ll a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    es[i] = edge{a, b, c};
  }
  ll sum = 0;
  {
    sort(es, es+M, comp);
    UnionFind uf(N);
    uf.initialize();
    ll cnt = 0;
    rep(i, M){
      edge& e = es[i];
      if(!uf.isSame(e.u, e.v)){
        uf.merge(e.u, e.v);
        es[cnt] = edge{e.u, e.v, e.cost};
        cnt++;
        sum += e.cost;
        G[e.u].push_back(make_pair(e.v, e.cost));
        G[e.v].push_back(make_pair(e.u, e.cost));
      }
    }
  }
  for(int i=0; i<N; i++){
    memset(visited, false, sizeof(visited));
    dfs(i, i);
  }

  ll Q;
  cin >> Q;
  rep(q, Q){
    ll s, t;
    cin >> s >> t;
    s--; t--;
    cout << sum-mx[s][t] << endl;
  }
}

```