#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

struct Edge{
    int from, to;
    ll cost;
    Edge(int from,int to,ll cost): from(from),to(to), cost(cost){}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

bool operator < (const Edge &e, const Edge &f){
    return e.cost > f.cost;
}

struct UF {
	vector<int> data;
	UF(int size) : data(size, -1) { }
	bool unite(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 find(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)];
	}
};

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

    int n,m;cin>>n>>m;
    Graph g(n);
    priority_queue<Edge> pq;
    for(int i=0;i<m;i++){
      int a,b;cin>>a>>b;a--;b--;
      ll c;cin>>c;
      pq.push(Edge(a,b,c));
      g[a].push_back(Edge(a,b,c));
      g[b].push_back(Edge(b,a,c));
    }
    ll sum=0;
    UF uf(n);
    Graph mst(n);
    while(!pq.empty()){
      Edge e=pq.top();pq.pop();
      if(uf.find(e.from,e.to)) continue;
      uf.unite(e.from,e.to);
      mst[e.from].push_back(Edge(e.from,e.to,e.cost));
      mst[e.to].push_back(Edge(e.to,e.from,e.cost));
      sum += e.cost;
    }
    vector<vector<ll>> dis(n,vector<ll>(n,-1));
    for(int i=0;i<n;i++){
      queue<int> q;
      dis[i][i]=0;
      q.push(i);
      while(!q.empty()){
        int v=q.front();q.pop();
        for(int j=0;j<(int)mst[v].size();j++){
          int next=mst[v][j].to;
          if(dis[i][next]!=-1) continue;
          dis[i][next]=max(dis[i][v], mst[v][j].cost);
          q.push(next);
        }
      }
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
      int s,t;cin>>s>>t;s--;t--;
      cout<<sum-dis[s][t]<<endl;
    }
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

struct Edge{
    int from, to;
    ll cost;
    Edge(int from,int to,ll cost): from(from),to(to), cost(cost){}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

bool operator < (const Edge &e, const Edge &f){
    return e.cost > f.cost;
}

struct UF {
	vector<int> data;
	UF(int size) : data(size, -1) { }
	bool unite(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 find(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)];
	}
};

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

    int n,m;cin>>n>>m;
    Graph g(n);
    priority_queue<Edge> pq;
    for(int i=0;i<m;i++){
      int a,b;cin>>a>>b;a--;b--;
      ll c;cin>>c;
      pq.push(Edge(a,b,c));
      g[a].push_back(Edge(a,b,c));
      g[b].push_back(Edge(b,a,c));
    }
    ll sum=0;
    UF uf(n);
    Graph mst(n);
    while(!pq.empty()){
      Edge e=pq.top();pq.pop();
      if(uf.find(e.from,e.to)) continue;
      uf.unite(e.from,e.to);
      mst[e.from].push_back(Edge(e.from,e.to,e.cost));
      mst[e.to].push_back(Edge(e.to,e.from,e.cost));
      sum += e.cost;
    }
    vector<vector<ll>> dis(n,vector<ll>(n,-1));
    for(int i=0;i<n;i++){
      queue<int> q;
      dis[i][i]=0;
      q.push(i);
      while(!q.empty()){
        int v=q.front();q.pop();
        for(int j=0;j<(int)mst[v].size();j++){
          int next=mst[v][j].to;
          if(dis[i][next]!=-1) continue;
          dis[i][next]=max(dis[i][v], mst[v][j].cost);
          q.push(next);
        }
      }
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
      int s,t;cin>>s>>t;s--;t--;
      cout<<sum-dis[s][t]<<endl;
    }
}

```