
#define TESTING

// INCLUDE
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <stack>
#include <queue>
#include <cassert>

using namespace std;

// types
typedef long long            int64 ;
typedef unsigned long long   uint64 ;
typedef unsigned char uchar;
typedef unsigned short ushort;
typedef int64 hash_type;

// Shortcuts
#define all(_xx)             _xx.begin(), _xx.end()
#define pb                   push_back
#define SS                   stringstream
#define mp(XX, YY)           make_pair(XX, YY)
#define fi                   first
#define se                   second

#define pii                  pair<int, int>
#define pcc                  pair<char, char>
#define pucc                 pair<uchar, uchar>
#define pll                  pair<long long, long long>
#define pdd                  pair<double, double>

#define vl                   vector<long long>
#define vs                   vector<string>
#define vd                   vector<double>
#define vc                   vector<char>
#define vi                   vector<int>
#define vvc                  vector<vector<char>>
#define vvi                  vector<vector<int>>
#define vvl                  vector<vector<long long>>
#define vpcc                 vector<pair<char,char> >
#define vpdd                 vector<pair<double,double> >
#define vpii                 vector<pair<int,int>> 
#define vpll                 vector<pair<long long,long long>> 

#define re(II, NN)           for (int II(0), _NN(NN); (II) < (_NN); ++(II))
#define fod(II, XX, YY)      for (int II(XX), _YY(YY); (II) >= (_YY); --(II))
#define fo(II, XX, YY)       for (int II(XX), _YY(YY); (II) <= (_YY); ++(II))

template <class T> int size (const T& value) {return value.size();}

// ostream operator for STL types: pair, vector, vector<vector>, set, unordered_set, map, unordered_map
template <class T>
std::ostream& PrintContainer (std::ostream& stream, const T& container) {
    for (auto el : container) stream << el << " "; return stream;
}

template<class T> std::ostream&  operator <<(std::ostream& stream, const set<T> & s) {
    return PrintContainer (stream, s);
}

template<class T> std::ostream&  operator <<(std::ostream& stream, const unordered_set<T> & s) {
    return PrintContainer (stream, s);
}

template<class T> std::ostream&  operator << (std::ostream& stream, const vector<T> & v) {
    return PrintContainer (stream, v);
}

template<class T, class V> std::ostream&  operator << (std::ostream& stream, const map<T, V> & m) {
    return PrintContainer (stream, m);
}

template<class T, class V> std::ostream&  operator << (std::ostream& stream, const unordered_map<T, V> & m) {
    return PrintContainer (stream, m);
}

template<class T, class V> std::ostream&  operator << (std::ostream& stream, const pair<T, V> & p) {
    stream << p.first << "," << p.second << " ";
    return stream;
}

template<class T> std::ostream&  operator <<(std::ostream& stream, const vector<vector<T> > & v) {
    for (auto line : v) { for (auto el : line) stream << el << " "; stream << "\n";}
    return stream;
}
// End ostream

// Variable debug, enabled with TESTING
#ifdef TESTING
// Adapted from http://codeforces.com/blog/entry/15643
vector<string> debug_split(const string& s, char c) {
    vector<string> v; stringstream ss(s); string x;
    while (getline(ss, x, c)) v.emplace_back(x); return move(v);}

void debug_err() {cerr << "\n";}
template<typename T, typename... Args>
void debug_err(vector<string>::iterator it, T a, Args... args) {
    cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " | ";
    debug_err(++it, args...);
}

class Debugger {
public:
    template <class T> void Output (const T& v) {cerr << v << " ";}
    template <class T> Debugger& operator , (const T& v) {Output(v);return *this;}
} dbg;

#define trace(args...) { vector<string> _v = debug_split(#args, ','); debug_err(_v.begin(), args); }
#define warn(args...) {dbg,args; cerr << "\n"; cerr.flush();}
#define echo(arg) {cerr << #arg << ": "; dbg,arg; cerr << "\n"; cerr.flush();}
#else
#define warn(args...) {}
#define echo(arg) {}
#define trace(args..) {}
#endif
// End debug

// Helper
template <typename U, typename V>
void remin (U& A, V B) {
    if (A > B) A = B;
}

template <typename U, typename V>
void remax (U& A, V B) {
    if (A < B) A = B;
}
//---- End of template code -----//
const int MAXN = 4001;

int N, M, Q;

vector<pair<int, pair<int, int>>> edges;
vector<vector<int>> g;

int answer[MAXN][MAXN];
int cost[MAXN][MAXN];
int64 tot_cost;

int parent[MAXN];

int find_parent(int x) {
    if (x != parent[x])
        return parent[x] = find_parent(parent[x]);
    return x;
}

void dfs(int x, int p, int el, int cur) {
    answer[el][x] = answer[x][el] = cur;
    for (auto v : g[x]) {
        if (v != p) {
            dfs(v, x, el, max(cur, cost[x][v]));
        }
    }
}

int main() {
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        edges.push_back(make_pair(c, make_pair(a, b)));
    }

    sort(edges.begin(), edges.end());

    for (int i = 0; i < N; i++)
        parent[i] = i;

    g.resize(N);

    //cerr << "?\n";

    for (auto e : edges) {
        int c = e.first;
        int a = e.second.first;
        int b = e.second.second;

        if (find_parent(a) != find_parent(b)) {
            tot_cost += c;
            if (rand() & 1) {
                parent[ parent[a] ] = parent[b];
            } else {
                parent[ parent[b] ] = parent[a];
            }
            g[a].push_back(b);
            g[b].push_back(a);

            cost[a][b] = c;
            cost[b][a] = c;

            //for (int i = 0; i < N; i++) cerr << parent[i] << " ";
            //cerr << "\n";
            //cerr << a << " " << b << "\n";
        }
    }

    //cerr << "dfs\n";

    for (int i = 0; i < N; i++)
        dfs(i, -1, i, 0);

    //cerr << "yeah\n";
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int S, T;
        cin >> S >> T;
        S--, T--;
        cout << tot_cost - answer[S][T] << "\n";
    }

    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

#define TESTING

// INCLUDE
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <stack>
#include <queue>
#include <cassert>

using namespace std;

// types
typedef long long            int64 ;
typedef unsigned long long   uint64 ;
typedef unsigned char uchar;
typedef unsigned short ushort;
typedef int64 hash_type;

// Shortcuts
#define all(_xx)             _xx.begin(), _xx.end()
#define pb                   push_back
#define SS                   stringstream
#define mp(XX, YY)           make_pair(XX, YY)
#define fi                   first
#define se                   second

#define pii                  pair<int, int>
#define pcc                  pair<char, char>
#define pucc                 pair<uchar, uchar>
#define pll                  pair<long long, long long>
#define pdd                  pair<double, double>

#define vl                   vector<long long>
#define vs                   vector<string>
#define vd                   vector<double>
#define vc                   vector<char>
#define vi                   vector<int>
#define vvc                  vector<vector<char>>
#define vvi                  vector<vector<int>>
#define vvl                  vector<vector<long long>>
#define vpcc                 vector<pair<char,char> >
#define vpdd                 vector<pair<double,double> >
#define vpii                 vector<pair<int,int>> 
#define vpll                 vector<pair<long long,long long>> 

#define re(II, NN)           for (int II(0), _NN(NN); (II) < (_NN); ++(II))
#define fod(II, XX, YY)      for (int II(XX), _YY(YY); (II) >= (_YY); --(II))
#define fo(II, XX, YY)       for (int II(XX), _YY(YY); (II) <= (_YY); ++(II))

template <class T> int size (const T& value) {return value.size();}

// ostream operator for STL types: pair, vector, vector<vector>, set, unordered_set, map, unordered_map
template <class T>
std::ostream& PrintContainer (std::ostream& stream, const T& container) {
    for (auto el : container) stream << el << " "; return stream;
}

template<class T> std::ostream&  operator <<(std::ostream& stream, const set<T> & s) {
    return PrintContainer (stream, s);
}

template<class T> std::ostream&  operator <<(std::ostream& stream, const unordered_set<T> & s) {
    return PrintContainer (stream, s);
}

template<class T> std::ostream&  operator << (std::ostream& stream, const vector<T> & v) {
    return PrintContainer (stream, v);
}

template<class T, class V> std::ostream&  operator << (std::ostream& stream, const map<T, V> & m) {
    return PrintContainer (stream, m);
}

template<class T, class V> std::ostream&  operator << (std::ostream& stream, const unordered_map<T, V> & m) {
    return PrintContainer (stream, m);
}

template<class T, class V> std::ostream&  operator << (std::ostream& stream, const pair<T, V> & p) {
    stream << p.first << "," << p.second << " ";
    return stream;
}

template<class T> std::ostream&  operator <<(std::ostream& stream, const vector<vector<T> > & v) {
    for (auto line : v) { for (auto el : line) stream << el << " "; stream << "\n";}
    return stream;
}
// End ostream

// Variable debug, enabled with TESTING
#ifdef TESTING
// Adapted from http://codeforces.com/blog/entry/15643
vector<string> debug_split(const string& s, char c) {
    vector<string> v; stringstream ss(s); string x;
    while (getline(ss, x, c)) v.emplace_back(x); return move(v);}

void debug_err() {cerr << "\n";}
template<typename T, typename... Args>
void debug_err(vector<string>::iterator it, T a, Args... args) {
    cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " | ";
    debug_err(++it, args...);
}

class Debugger {
public:
    template <class T> void Output (const T& v) {cerr << v << " ";}
    template <class T> Debugger& operator , (const T& v) {Output(v);return *this;}
} dbg;

#define trace(args...) { vector<string> _v = debug_split(#args, ','); debug_err(_v.begin(), args); }
#define warn(args...) {dbg,args; cerr << "\n"; cerr.flush();}
#define echo(arg) {cerr << #arg << ": "; dbg,arg; cerr << "\n"; cerr.flush();}
#else
#define warn(args...) {}
#define echo(arg) {}
#define trace(args..) {}
#endif
// End debug

// Helper
template <typename U, typename V>
void remin (U& A, V B) {
    if (A > B) A = B;
}

template <typename U, typename V>
void remax (U& A, V B) {
    if (A < B) A = B;
}
//---- End of template code -----//
const int MAXN = 4001;

int N, M, Q;

vector<pair<int, pair<int, int>>> edges;
vector<vector<int>> g;

int answer[MAXN][MAXN];
int cost[MAXN][MAXN];
int64 tot_cost;

int parent[MAXN];

int find_parent(int x) {
    if (x != parent[x])
        return parent[x] = find_parent(parent[x]);
    return x;
}

void dfs(int x, int p, int el, int cur) {
    answer[el][x] = answer[x][el] = cur;
    for (auto v : g[x]) {
        if (v != p) {
            dfs(v, x, el, max(cur, cost[x][v]));
        }
    }
}

int main() {
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        edges.push_back(make_pair(c, make_pair(a, b)));
    }

    sort(edges.begin(), edges.end());

    for (int i = 0; i < N; i++)
        parent[i] = i;

    g.resize(N);

    //cerr << "?\n";

    for (auto e : edges) {
        int c = e.first;
        int a = e.second.first;
        int b = e.second.second;

        if (find_parent(a) != find_parent(b)) {
            tot_cost += c;
            if (rand() & 1) {
                parent[ parent[a] ] = parent[b];
            } else {
                parent[ parent[b] ] = parent[a];
            }
            g[a].push_back(b);
            g[b].push_back(a);

            cost[a][b] = c;
            cost[b][a] = c;

            //for (int i = 0; i < N; i++) cerr << parent[i] << " ";
            //cerr << "\n";
            //cerr << a << " " << b << "\n";
        }
    }

    //cerr << "dfs\n";

    for (int i = 0; i < N; i++)
        dfs(i, -1, i, 0);

    //cerr << "yeah\n";
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int S, T;
        cin >> S >> T;
        S--, T--;
        cout << tot_cost - answer[S][T] << "\n";
    }

    return 0;
}

```