#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll unipar[4010];
ll unilen[4010];
vector<pll> vn[4010];
struct edge{
  ll len,from,to;
};
bool cmp(edge& a,edge& b){
  return a.len<b.len;
}
void uniinit(ll n){
  for(ll i=1;i<=n;i++){
    unipar[i]=i;
    unilen[i]=0;
  }
}
ll root(ll n){
  if(unipar[n]==n)return n;
  return unipar[n]=root(unipar[n]);
}
void unit(ll a,ll b){
  a=root(a);
  b=root(b);
  if(a==b)return;
  if(unilen[a]<unilen[b]){
    unipar[a]=b;
  }
  else{
    unipar[b]=a;
    if(unipar[b]==unipar[a])unilen[a]++;
  }
}
ll ne;
ll par[60][4010];
ll dep[4010];
void lcadfs(ll v,ll p,ll d){
  par[0][v]=p;
  dep[v]=d;
  for(ll i=0;i<vn[v].size();i++){
    if(vn[v][i].first!=p)lcadfs(vn[v][i].first,v,d+1);
  }
}
void lcainit(ll n){
  lcadfs(ne,-1,0);
  for(ll i=0;i<59;i++){
    for(ll j=1;j<=n;j++){
      if(par[i][j]<0)par[i+1][j]=-1;
      else par[i+1][j]=par[i][par[i][j]];
    }
  }
}
ll lca(ll u,ll v){
  if(dep[u]>dep[v])swap(u,v);
  for(ll i=0;i<60;i++){
    if((dep[v]-dep[u])>>i&1)v=par[i][v];
  }
  if(u==v)return u;
  for(ll i=59;i>=0;i--){
    if(par[i][u]!=par[i][v]){
      u=par[i][u];
      v=par[i][v];
    }
  }
  return par[0][u];
}
ll mae[60][4010];
void maedfs(ll v,ll p,ll dis){
  mae[0][v]=dis;
  for(ll i=0;i<vn[v].size();i++){
    if(vn[v][i].first!=p)maedfs(vn[v][i].first,v,vn[v][i].second);
  }
}
void maeinit(ll n){
  maedfs(ne,-1,-1);
  for(ll i=0;i<59;i++){
    for(ll j=1;j<=n;j++){
      if(par[i][j]<0)mae[i+1][j]=-1;
      else mae[i+1][j]=max(mae[i][j],mae[i][par[i][j]]);
    }
  }
}
ll maxedge(ll u,ll v){
  ll r=lca(u,v);
  ll ret=0;
  for(ll i=59;i>=0;i--){
    if((dep[u]-dep[r])>>i&1){
      ret=max(ret,mae[i][u]);
      u=par[i][u];
    }
  }
  for(ll i=59;i>=0;i--){
    if((dep[v]-dep[r])>>i&1){
      ret=max(ret,mae[i][v]);
      v=par[i][v];
    }
  }
  return ret;
}
int main(){
  ll n,m;cin>>n>>m;
  vector<edge> v;
  for(ll i=0;i<m;i++){
    ll a,b,c;cin>>a>>b>>c;
    v.push_back((edge){c,a,b});
  }
  sort(v.begin(),v.end(),cmp);
  uniinit(n);
  ll now=0;
  ll sum=0;
  for(ll i=0;i<m;i++){
    edge e=v[i];
    ll a=e.from,b=e.to;
    if(root(a)!=root(b)){
      unit(a,b);
      sum+=e.len;
      vn[a].push_back(make_pair(b,e.len));
      vn[b].push_back(make_pair(a,e.len));
      now++;
    }
    if(now==n-1)break;
  }
  ne=1;
  lcainit(n);
  maeinit(n);
  ll q;cin>>q;
  for(ll i=0;i<q;i++){
    ll s,t;cin>>s>>t;
    ll dd=maxedge(s,t);
    cout<<sum-dd<<endl;
  }
  //cout<<maxedge(5,7)<<endl;
  //for(ll i=0;i<10;i++){
    //for(ll j=1;j<=7;j++)cout<<par[i][j]<<" ";
    //cout<<endl;
  //}
}
### Prompt

Your challenge is to write 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 ll;
typedef pair<ll,ll> pll;
ll unipar[4010];
ll unilen[4010];
vector<pll> vn[4010];
struct edge{
  ll len,from,to;
};
bool cmp(edge& a,edge& b){
  return a.len<b.len;
}
void uniinit(ll n){
  for(ll i=1;i<=n;i++){
    unipar[i]=i;
    unilen[i]=0;
  }
}
ll root(ll n){
  if(unipar[n]==n)return n;
  return unipar[n]=root(unipar[n]);
}
void unit(ll a,ll b){
  a=root(a);
  b=root(b);
  if(a==b)return;
  if(unilen[a]<unilen[b]){
    unipar[a]=b;
  }
  else{
    unipar[b]=a;
    if(unipar[b]==unipar[a])unilen[a]++;
  }
}
ll ne;
ll par[60][4010];
ll dep[4010];
void lcadfs(ll v,ll p,ll d){
  par[0][v]=p;
  dep[v]=d;
  for(ll i=0;i<vn[v].size();i++){
    if(vn[v][i].first!=p)lcadfs(vn[v][i].first,v,d+1);
  }
}
void lcainit(ll n){
  lcadfs(ne,-1,0);
  for(ll i=0;i<59;i++){
    for(ll j=1;j<=n;j++){
      if(par[i][j]<0)par[i+1][j]=-1;
      else par[i+1][j]=par[i][par[i][j]];
    }
  }
}
ll lca(ll u,ll v){
  if(dep[u]>dep[v])swap(u,v);
  for(ll i=0;i<60;i++){
    if((dep[v]-dep[u])>>i&1)v=par[i][v];
  }
  if(u==v)return u;
  for(ll i=59;i>=0;i--){
    if(par[i][u]!=par[i][v]){
      u=par[i][u];
      v=par[i][v];
    }
  }
  return par[0][u];
}
ll mae[60][4010];
void maedfs(ll v,ll p,ll dis){
  mae[0][v]=dis;
  for(ll i=0;i<vn[v].size();i++){
    if(vn[v][i].first!=p)maedfs(vn[v][i].first,v,vn[v][i].second);
  }
}
void maeinit(ll n){
  maedfs(ne,-1,-1);
  for(ll i=0;i<59;i++){
    for(ll j=1;j<=n;j++){
      if(par[i][j]<0)mae[i+1][j]=-1;
      else mae[i+1][j]=max(mae[i][j],mae[i][par[i][j]]);
    }
  }
}
ll maxedge(ll u,ll v){
  ll r=lca(u,v);
  ll ret=0;
  for(ll i=59;i>=0;i--){
    if((dep[u]-dep[r])>>i&1){
      ret=max(ret,mae[i][u]);
      u=par[i][u];
    }
  }
  for(ll i=59;i>=0;i--){
    if((dep[v]-dep[r])>>i&1){
      ret=max(ret,mae[i][v]);
      v=par[i][v];
    }
  }
  return ret;
}
int main(){
  ll n,m;cin>>n>>m;
  vector<edge> v;
  for(ll i=0;i<m;i++){
    ll a,b,c;cin>>a>>b>>c;
    v.push_back((edge){c,a,b});
  }
  sort(v.begin(),v.end(),cmp);
  uniinit(n);
  ll now=0;
  ll sum=0;
  for(ll i=0;i<m;i++){
    edge e=v[i];
    ll a=e.from,b=e.to;
    if(root(a)!=root(b)){
      unit(a,b);
      sum+=e.len;
      vn[a].push_back(make_pair(b,e.len));
      vn[b].push_back(make_pair(a,e.len));
      now++;
    }
    if(now==n-1)break;
  }
  ne=1;
  lcainit(n);
  maeinit(n);
  ll q;cin>>q;
  for(ll i=0;i<q;i++){
    ll s,t;cin>>s>>t;
    ll dd=maxedge(s,t);
    cout<<sum-dd<<endl;
  }
  //cout<<maxedge(5,7)<<endl;
  //for(ll i=0;i<10;i++){
    //for(ll j=1;j<=7;j++)cout<<par[i][j]<<" ";
    //cout<<endl;
  //}
}
```