#include <vector>
#include <queue>
#include <cstdio>
using namespace std;

typedef long long Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(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 findSet(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)];
  }
};

Graph opt; //optimal edges for minimum-spanning
vector<vector<int>> max_edge;
Weight minimumSpanningForest(const Graph &g) {
  int n = g.size();
  priority_queue<Edge> Q;
  for(int u=0;u<n;u++) for(auto &e: g[u]) /*if (u < e->dst)*/ Q.push(e);
  UnionFind uf(n);

  Weight total = 0;
  Edges F;
  while (F.size() < n-1 && !Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (uf.unionSet(e.src, e.dst)) {
      F.push_back(e);
      total += e.weight;
      opt[e.src].emplace_back(e.src,e.dst,e.weight);
      opt[e.dst].emplace_back(e.dst,e.src,e.weight);
    }
  }
  return total; //pair<Weight, Edges>(total, F);
}

void dfs(int z,int c,long long k,vector<int>&v){
	max_edge[z][c]=k;
	v[c]=1;
	for(auto &e:opt[c])if(!v[e.dst])dfs(z,e.dst,max(k,e.weight),v);
}

int main(){
	int N,M,Q,a,b,c;
	scanf("%d%d",&N,&M);
	opt.resize(N);
	Weight w;
	{
		Graph g(N);
		for(;M--;){
			scanf("%d%d%d",&a,&b,&c);
			g[a-1].emplace_back(a-1,b-1,c);
		}
		w=minimumSpanningForest(g);
	}
	max_edge.resize(N);
	for(int i=0;i<N;i++)max_edge[i].resize(N);
	for(int i=0;i<N;i++){
		vector<int>v(N);
		dfs(i,i,0,v);
	}
	scanf("%d",&Q);
	for(;Q--;){
		scanf("%d%d",&a,&b);
		printf("%lld\n",w-max_edge[a-1][b-1]);
	}
}
### 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 <vector>
#include <queue>
#include <cstdio>
using namespace std;

typedef long long Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(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 findSet(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)];
  }
};

Graph opt; //optimal edges for minimum-spanning
vector<vector<int>> max_edge;
Weight minimumSpanningForest(const Graph &g) {
  int n = g.size();
  priority_queue<Edge> Q;
  for(int u=0;u<n;u++) for(auto &e: g[u]) /*if (u < e->dst)*/ Q.push(e);
  UnionFind uf(n);

  Weight total = 0;
  Edges F;
  while (F.size() < n-1 && !Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (uf.unionSet(e.src, e.dst)) {
      F.push_back(e);
      total += e.weight;
      opt[e.src].emplace_back(e.src,e.dst,e.weight);
      opt[e.dst].emplace_back(e.dst,e.src,e.weight);
    }
  }
  return total; //pair<Weight, Edges>(total, F);
}

void dfs(int z,int c,long long k,vector<int>&v){
	max_edge[z][c]=k;
	v[c]=1;
	for(auto &e:opt[c])if(!v[e.dst])dfs(z,e.dst,max(k,e.weight),v);
}

int main(){
	int N,M,Q,a,b,c;
	scanf("%d%d",&N,&M);
	opt.resize(N);
	Weight w;
	{
		Graph g(N);
		for(;M--;){
			scanf("%d%d%d",&a,&b,&c);
			g[a-1].emplace_back(a-1,b-1,c);
		}
		w=minimumSpanningForest(g);
	}
	max_edge.resize(N);
	for(int i=0;i<N;i++)max_edge[i].resize(N);
	for(int i=0;i<N;i++){
		vector<int>v(N);
		dfs(i,i,0,v);
	}
	scanf("%d",&Q);
	for(;Q--;){
		scanf("%d%d",&a,&b);
		printf("%lld\n",w-max_edge[a-1][b-1]);
	}
}
```