#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

class UnionFind{
private:
  vector<int> par, rank;
public:
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

  //find root of x
  int find(int x){
	if(par[x] == x)
	  return x;
	return (par[x] = find(par[x]));
  }

  void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y])
	  par[x] = y;
	else{
	  par[y] = x;
	  if(rank[x] == rank[y])
		++rank[x];
	}
  }

  bool same(int x, int y){
	return find(x) == find(y);
  }
};

struct Edge{
  int to;
  LL cost;

  Edge(int t, LL c): to(t), cost(c)
  {}
  bool operator>(const Edge& rhs) const{
	return cost > rhs.cost;
  }
  bool operator<(const Edge& rhs) const{
	return cost < rhs.cost;
  }

};
typedef vector< vector<Edge> > Graph;

// 無向グラフのとき
void add_edge(Graph& graph, int u, int v, LL cost){
  graph[u].push_back(Edge(v,cost));
  graph[v].push_back(Edge(u,cost));
}

vector<pair<Edge,int>> edges;
LL kruskal(const Graph& G, Graph& G_){
  int N = SZ(G);
  UnionFind uf(N);

  LL res = 0, i, n = 0;
  for(i=0;i<SZ(edges);++i){
	auto& e = edges[i].first;
	int v = edges[i].second;
	if(!uf.same(e.to,v)){
	  uf.unite(e.to, v);
	  res += e.cost;
	  add_edge(G_, e.to, v, e.cost);
	}
  }
  return res;
}

LL dist[4010][4010];
void dfs(int s, int p, int u, LL mx, Graph& G){
  dist[s][u] = dist[u][s] = max(dist[s][u], mx);
  for(auto& e: G[u]){
	if(e.to == p) continue;
	dfs(s, u, e.to, max(mx,e.cost), G);
  }
}

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

  int N, M; cin >> N >> M;
  Graph G(N), G_(N);
  REP(i,M){
	int a, b, c; cin >> a >> b >> c;
	--a; --b;
	add_edge(G, a, b, c);
	edges.push_back(MP(G[a].back(), a));
	edges.push_back(MP(G[b].back(), b));
  }
  sort(ALL(edges));

  LL mx = kruskal(G,G_);
  REP(i,N) dfs(i,-1,i,0,G_);
  int Q; cin >> Q;
  while(Q--){
	LL s,t; cin >> s >> t;
	--s, --t;

	cout << mx - dist[s][t] << endl;
  }

  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

class UnionFind{
private:
  vector<int> par, rank;
public:
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

  //find root of x
  int find(int x){
	if(par[x] == x)
	  return x;
	return (par[x] = find(par[x]));
  }

  void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y])
	  par[x] = y;
	else{
	  par[y] = x;
	  if(rank[x] == rank[y])
		++rank[x];
	}
  }

  bool same(int x, int y){
	return find(x) == find(y);
  }
};

struct Edge{
  int to;
  LL cost;

  Edge(int t, LL c): to(t), cost(c)
  {}
  bool operator>(const Edge& rhs) const{
	return cost > rhs.cost;
  }
  bool operator<(const Edge& rhs) const{
	return cost < rhs.cost;
  }

};
typedef vector< vector<Edge> > Graph;

// 無向グラフのとき
void add_edge(Graph& graph, int u, int v, LL cost){
  graph[u].push_back(Edge(v,cost));
  graph[v].push_back(Edge(u,cost));
}

vector<pair<Edge,int>> edges;
LL kruskal(const Graph& G, Graph& G_){
  int N = SZ(G);
  UnionFind uf(N);

  LL res = 0, i, n = 0;
  for(i=0;i<SZ(edges);++i){
	auto& e = edges[i].first;
	int v = edges[i].second;
	if(!uf.same(e.to,v)){
	  uf.unite(e.to, v);
	  res += e.cost;
	  add_edge(G_, e.to, v, e.cost);
	}
  }
  return res;
}

LL dist[4010][4010];
void dfs(int s, int p, int u, LL mx, Graph& G){
  dist[s][u] = dist[u][s] = max(dist[s][u], mx);
  for(auto& e: G[u]){
	if(e.to == p) continue;
	dfs(s, u, e.to, max(mx,e.cost), G);
  }
}

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

  int N, M; cin >> N >> M;
  Graph G(N), G_(N);
  REP(i,M){
	int a, b, c; cin >> a >> b >> c;
	--a; --b;
	add_edge(G, a, b, c);
	edges.push_back(MP(G[a].back(), a));
	edges.push_back(MP(G[b].back(), b));
  }
  sort(ALL(edges));

  LL mx = kruskal(G,G_);
  REP(i,N) dfs(i,-1,i,0,G_);
  int Q; cin >> Q;
  while(Q--){
	LL s,t; cin >> s >> t;
	--s, --t;

	cout << mx - dist[s][t] << endl;
  }

  return 0;
}

```