#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
template <typename K, typename V>
using umap = unordered_map<K, V>;
template <typename K>
using uset = unordered_set<K>;
using vi = vec<int>;
using vl = vec<ll>;
using vpi = vec<pii>;
using vpl = vec<pll>;
using int128 = __int128_t;
using uint128 = __uint128_t;
template <typename I>
string intStr(I x) {
  string ret;
  while (x > 0) {
    ret += (x % 10) + '0';
    x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
template <typename T>
inline void maxa(T& st, T v) {
  st = max(st, v);
}
template <typename T>
inline void mina(T& st, T v) {
  st = min(st, v);
}
inline void setprec(ostream& out, int prec) {
  out << setprecision(prec) << fixed;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> iter) {
  out << "[";
  for (auto t : iter) {
    out << t << ", ";
  }
  out << "]";
  return out;
}
template <typename T>
string arrayStr(T* arr, int sz) {
  string ret = "[";
  for (int i = 0; i < sz; i++) {
    ret += to_string(arr[i]) + ", ";
  }
  return ret + "]";
}
template <typename T>
void printArray(T* arr, int sz) {
  for (int i = 0; i < sz; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}
inline void scan() {}
template <typename F, typename... R>
inline void scan(F& f, R&... r) {
  cin >> f;
  scan(r...);
}
template <typename F>
inline void println(F t) {
  cout << t << '\n';
}
template <typename F, typename... R>
inline void println(F f, R... r) {
  cout << f << " ";
  println(r...);
}
inline void print() {}
template <typename F, typename... R>
inline void print(F f, R... r) {
  cout << f;
  print(r...);
}
template <typename F>
inline string __generic_tostring(F f) {
  stringstream ss;
  ss << f;
  return ss.str();
}
template <typename F>
inline string __join_comma(F f) {
  return __generic_tostring(f);
}
template <typename F, typename... R>
string __join_comma(F f, R... r) {
  return __generic_tostring(f) + ", " + __join_comma(r...);
}
struct Ed {
  int v;
  ll w;
};
const int MN = 1e5 + 1, LG = 18, D = 21;
int N, M, Q, A[MN], B[MN], W[MN];
vec<Ed> g[MN];
struct DSU {
  vector<int> dsu;
  void init(int N) {
    dsu.resize(N);
    iota(dsu.begin(), dsu.end(), 0);
  }
  int rt(int x) { return dsu[x] == x ? x : dsu[x] = rt(dsu[x]); }
  void merge(int x, int y) { dsu[rt(x)] = rt(y); }
  bool same(int x, int y) { return rt(x) == rt(y); }
};
int tb[LG][MN], lv[MN];
ll disTree[MN];
void dfsLca(int c, int p, int clv, ll cdis) {
  lv[c] = clv;
  disTree[c] = cdis;
  tb[0][c] = p;
  for (auto to : g[c])
    if (to.v ^ p) dfsLca(to.v, c, clv + 1, cdis + to.w);
}
void initSp() {
  memset(tb, -1, sizeof tb);
  dfsLca(1, -1, 0, 0);
  for (int i = 1; i < LG; i++) {
    for (int j = 1; j <= N; j++) {
      int pp = tb[i - 1][j];
      tb[i][j] = pp == -1 ? -1 : tb[i - 1][pp];
    }
  }
}
int lca(int a, int b) {
  if (a == b) return a;
  if (lv[a] > lv[b]) swap(a, b);
  int delta = lv[b] - lv[a];
  for (int i = 0; i < LG; i++)
    if ((delta >> i) & 1) b = tb[i][b];
  if (a == b) return a;
  for (int i = LG - 1; i >= 0; i--) {
    if (tb[i][a] != tb[i][b]) {
      a = tb[i][a];
      b = tb[i][b];
    }
  }
  return tb[0][a];
}
ll qdis(int a, int b) {
  return disTree[a] + disTree[b] - 2 * disTree[lca(a, b)];
}
map<int, int> extraMp;
vi extra;
DSU uf;
ll qdisNE(int node, int edge) {
  return min(qdis(node, A[edge]), qdis(node, B[edge]));
}
ll qdisEE(int edge1, int edge2) {
  return min(qdisNE(A[edge1], edge2), qdisNE(B[edge1], edge2));
}
ll dis[D][D], precalc[D][MN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  scan(N, M);
  int ptr = 0;
  uf.init(N + 1);
  for (__typeof(0) i = 0; i < M; i++) {
    scan(A[i], B[i], W[i]);
    if (!uf.same(A[i], B[i])) {
      g[A[i]].push_back({B[i], W[i]});
      g[B[i]].push_back({A[i], W[i]});
      uf.merge(A[i], B[i]);
    } else {
      extra.push_back(i);
      extraMp[i] = ptr++;
    }
  }
  initSp();
  int cnt = M - N + 1;
  for (__typeof(0) i = 0; i < cnt; i++)
    for (__typeof(0) j = 0; j < cnt; j++)
      dis[i][j] = qdisEE(extra[i], extra[j]);
  for (__typeof(0) k = 0; k < cnt; k++) {
    for (__typeof(0) i = 0; i < cnt; i++) {
      for (__typeof(0) j = 0; j < cnt; j++) {
        mina(dis[i][j], dis[i][k] + dis[k][j] + W[extra[k]]);
      }
    }
  }
  for (__typeof(0) i = 0; i < cnt; i++) {
    for (__typeof(1) j = 1; j < N + 1; j++) {
      precalc[i][j] = qdisNE(j, extra[i]);
    }
  }
  scan(Q);
  while (Q--) {
    int u, v;
    scan(u, v);
    ll best = qdis(u, v);
    for (__typeof(0) i = 0; i < cnt; i++) {
      mina(best, precalc[i][u] + precalc[i][v] + W[extra[i]]);
      for (__typeof(0) j = 0; j < cnt; j++) {
        if (i == j) continue;
        mina(best, precalc[i][u] + dis[i][j] + precalc[j][v] + W[extra[i]] +
                       W[extra[j]]);
      }
    }
    println(best);
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

You are given a weighed undirected connected graph, consisting of n vertices and m edges.

You should answer q queries, the i-th query is to find the shortest distance between vertices u_i and v_i.

Input

The first line contains two integers n and m~(1 ≤ n, m ≤ 10^5, m - n ≤ 20) — the number of vertices and edges in the graph.

Next m lines contain the edges: the i-th edge is a triple of integers v_i, u_i, d_i~(1 ≤ u_i, v_i ≤ n, 1 ≤ d_i ≤ 10^9, u_i ≠ v_i). This triple means that there is an edge between vertices u_i and v_i of weight d_i. It is guaranteed that graph contains no self-loops and multiple edges.

The next line contains a single integer q~(1 ≤ q ≤ 10^5) — the number of queries.

Each of the next q lines contains two integers u_i and v_i~(1 ≤ u_i, v_i ≤ n) — descriptions of the queries.

Pay attention to the restriction m - n ~ ≤ ~ 20.

Output

Print q lines.

The i-th line should contain the answer to the i-th query — the shortest distance between vertices u_i and v_i.

Examples

Input

3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3


Output

3
4
1


Input

8 13
1 2 4
2 3 6
3 4 1
4 5 12
5 6 3
6 7 8
7 8 7
1 4 1
1 8 3
2 6 9
2 7 1
4 6 3
6 8 2
8
1 5
1 7
2 3
2 8
3 7
3 4
6 8
7 8


Output

7
5
6
7
7
1
2
7

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
template <typename K, typename V>
using umap = unordered_map<K, V>;
template <typename K>
using uset = unordered_set<K>;
using vi = vec<int>;
using vl = vec<ll>;
using vpi = vec<pii>;
using vpl = vec<pll>;
using int128 = __int128_t;
using uint128 = __uint128_t;
template <typename I>
string intStr(I x) {
  string ret;
  while (x > 0) {
    ret += (x % 10) + '0';
    x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
template <typename T>
inline void maxa(T& st, T v) {
  st = max(st, v);
}
template <typename T>
inline void mina(T& st, T v) {
  st = min(st, v);
}
inline void setprec(ostream& out, int prec) {
  out << setprecision(prec) << fixed;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> iter) {
  out << "[";
  for (auto t : iter) {
    out << t << ", ";
  }
  out << "]";
  return out;
}
template <typename T>
string arrayStr(T* arr, int sz) {
  string ret = "[";
  for (int i = 0; i < sz; i++) {
    ret += to_string(arr[i]) + ", ";
  }
  return ret + "]";
}
template <typename T>
void printArray(T* arr, int sz) {
  for (int i = 0; i < sz; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}
inline void scan() {}
template <typename F, typename... R>
inline void scan(F& f, R&... r) {
  cin >> f;
  scan(r...);
}
template <typename F>
inline void println(F t) {
  cout << t << '\n';
}
template <typename F, typename... R>
inline void println(F f, R... r) {
  cout << f << " ";
  println(r...);
}
inline void print() {}
template <typename F, typename... R>
inline void print(F f, R... r) {
  cout << f;
  print(r...);
}
template <typename F>
inline string __generic_tostring(F f) {
  stringstream ss;
  ss << f;
  return ss.str();
}
template <typename F>
inline string __join_comma(F f) {
  return __generic_tostring(f);
}
template <typename F, typename... R>
string __join_comma(F f, R... r) {
  return __generic_tostring(f) + ", " + __join_comma(r...);
}
struct Ed {
  int v;
  ll w;
};
const int MN = 1e5 + 1, LG = 18, D = 21;
int N, M, Q, A[MN], B[MN], W[MN];
vec<Ed> g[MN];
struct DSU {
  vector<int> dsu;
  void init(int N) {
    dsu.resize(N);
    iota(dsu.begin(), dsu.end(), 0);
  }
  int rt(int x) { return dsu[x] == x ? x : dsu[x] = rt(dsu[x]); }
  void merge(int x, int y) { dsu[rt(x)] = rt(y); }
  bool same(int x, int y) { return rt(x) == rt(y); }
};
int tb[LG][MN], lv[MN];
ll disTree[MN];
void dfsLca(int c, int p, int clv, ll cdis) {
  lv[c] = clv;
  disTree[c] = cdis;
  tb[0][c] = p;
  for (auto to : g[c])
    if (to.v ^ p) dfsLca(to.v, c, clv + 1, cdis + to.w);
}
void initSp() {
  memset(tb, -1, sizeof tb);
  dfsLca(1, -1, 0, 0);
  for (int i = 1; i < LG; i++) {
    for (int j = 1; j <= N; j++) {
      int pp = tb[i - 1][j];
      tb[i][j] = pp == -1 ? -1 : tb[i - 1][pp];
    }
  }
}
int lca(int a, int b) {
  if (a == b) return a;
  if (lv[a] > lv[b]) swap(a, b);
  int delta = lv[b] - lv[a];
  for (int i = 0; i < LG; i++)
    if ((delta >> i) & 1) b = tb[i][b];
  if (a == b) return a;
  for (int i = LG - 1; i >= 0; i--) {
    if (tb[i][a] != tb[i][b]) {
      a = tb[i][a];
      b = tb[i][b];
    }
  }
  return tb[0][a];
}
ll qdis(int a, int b) {
  return disTree[a] + disTree[b] - 2 * disTree[lca(a, b)];
}
map<int, int> extraMp;
vi extra;
DSU uf;
ll qdisNE(int node, int edge) {
  return min(qdis(node, A[edge]), qdis(node, B[edge]));
}
ll qdisEE(int edge1, int edge2) {
  return min(qdisNE(A[edge1], edge2), qdisNE(B[edge1], edge2));
}
ll dis[D][D], precalc[D][MN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  scan(N, M);
  int ptr = 0;
  uf.init(N + 1);
  for (__typeof(0) i = 0; i < M; i++) {
    scan(A[i], B[i], W[i]);
    if (!uf.same(A[i], B[i])) {
      g[A[i]].push_back({B[i], W[i]});
      g[B[i]].push_back({A[i], W[i]});
      uf.merge(A[i], B[i]);
    } else {
      extra.push_back(i);
      extraMp[i] = ptr++;
    }
  }
  initSp();
  int cnt = M - N + 1;
  for (__typeof(0) i = 0; i < cnt; i++)
    for (__typeof(0) j = 0; j < cnt; j++)
      dis[i][j] = qdisEE(extra[i], extra[j]);
  for (__typeof(0) k = 0; k < cnt; k++) {
    for (__typeof(0) i = 0; i < cnt; i++) {
      for (__typeof(0) j = 0; j < cnt; j++) {
        mina(dis[i][j], dis[i][k] + dis[k][j] + W[extra[k]]);
      }
    }
  }
  for (__typeof(0) i = 0; i < cnt; i++) {
    for (__typeof(1) j = 1; j < N + 1; j++) {
      precalc[i][j] = qdisNE(j, extra[i]);
    }
  }
  scan(Q);
  while (Q--) {
    int u, v;
    scan(u, v);
    ll best = qdis(u, v);
    for (__typeof(0) i = 0; i < cnt; i++) {
      mina(best, precalc[i][u] + precalc[i][v] + W[extra[i]]);
      for (__typeof(0) j = 0; j < cnt; j++) {
        if (i == j) continue;
        mina(best, precalc[i][u] + dis[i][j] + precalc[j][v] + W[extra[i]] +
                       W[extra[j]]);
      }
    }
    println(best);
  }
  return 0;
}

```