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

#define fi first
#define se second
#define mk(a,b) make_pair(a,b)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plpll;
typedef pair<pll, pll> llll;

int N, M;
vector<pll> G[4010];
vector<pll> T[4010];
vector<pll> cost;
vector<plpll> E;
bool is_tree[400010];
int par[4010];
ll sum;
int current_root;
ll max_cost[4010][4010];

void init(int N)
{
    for(int i = 0; i < N; i++)par[i] = i;
    return;
}

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

void unite(int x, int y)
{
    x = root(x);
    y = root(y);

    if(x == y)return;

    par[x] = y;
    return;
}

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

void DFS(int v, int p = -1, ll d = 0)
{
    max_cost[current_root][v] = d;
    for(int i = 0; i < T[v].size(); i++)
    {
        int next = T[v][i].fi, id = T[v][i].se;
        ll cost = E[id].fi;
        if(p == next || !is_tree[id])continue;
        DFS(next, v, max(d, cost));
    }
    return;
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < M; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        cost.push_back(mk(c, i));
        E.push_back(mk(c, mk(a, b)));
        G[a].push_back(mk(b, i));
        G[b].push_back(mk(a, i));
    }

    init(N);
    sort(cost.begin(), cost.end());
    for(int i = 0; i < M; i++)
    {
        int now = cost[i].se;
        int a = E[now].se.fi, b = E[now].se.se;
        if(!same(a, b))
        {
            sum += cost[i].fi;
            T[a].push_back(mk(b, now));
            T[b].push_back(mk(a, now));
            is_tree[now] = true;
            unite(a, b);
        }
    }

    for(int i = 1; i <= N; i++)
    {
        current_root = i;
        DFS(i);
    }

    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << sum - max_cost[a][b] << endl;
    }
}

### Prompt

In Cpp, your task is to solve 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;

#define fi first
#define se second
#define mk(a,b) make_pair(a,b)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plpll;
typedef pair<pll, pll> llll;

int N, M;
vector<pll> G[4010];
vector<pll> T[4010];
vector<pll> cost;
vector<plpll> E;
bool is_tree[400010];
int par[4010];
ll sum;
int current_root;
ll max_cost[4010][4010];

void init(int N)
{
    for(int i = 0; i < N; i++)par[i] = i;
    return;
}

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

void unite(int x, int y)
{
    x = root(x);
    y = root(y);

    if(x == y)return;

    par[x] = y;
    return;
}

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

void DFS(int v, int p = -1, ll d = 0)
{
    max_cost[current_root][v] = d;
    for(int i = 0; i < T[v].size(); i++)
    {
        int next = T[v][i].fi, id = T[v][i].se;
        ll cost = E[id].fi;
        if(p == next || !is_tree[id])continue;
        DFS(next, v, max(d, cost));
    }
    return;
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < M; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        cost.push_back(mk(c, i));
        E.push_back(mk(c, mk(a, b)));
        G[a].push_back(mk(b, i));
        G[b].push_back(mk(a, i));
    }

    init(N);
    sort(cost.begin(), cost.end());
    for(int i = 0; i < M; i++)
    {
        int now = cost[i].se;
        int a = E[now].se.fi, b = E[now].se.se;
        if(!same(a, b))
        {
            sum += cost[i].fi;
            T[a].push_back(mk(b, now));
            T[b].push_back(mk(a, now));
            is_tree[now] = true;
            unite(a, b);
        }
    }

    for(int i = 1; i <= N; i++)
    {
        current_root = i;
        DFS(i);
    }

    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << sum - max_cost[a][b] << endl;
    }
}

```