#include <bits/stdc++.h>
using namespace std;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << a << "\n";
  err(++it, args...);
}
template <class T1, class T2, class T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple() : a(T1()), b(T2()), c(T3()){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <class T1, class T2, class T3>
bool operator<(const triple<T1, T2, T3>& t1, const triple<T1, T2, T3>& t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else if (t1.b != t2.b)
    return t1.b < t2.b;
  else
    return t1.c < t2.c;
}
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  return os << "(" << p.first << ": " << p.second << ")";
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  bool first = true;
  os << "[";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::set<T>& v) {
  bool first = true;
  os << "{";
  for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "}";
}
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os, const std::map<T1, T2>& v) {
  bool first = true;
  os << "{";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "}";
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os,
                                const std::unordered_set<T>& v) {
  return os << std::set<T>(v.begin(), v.end());
}
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os,
                                const std::unordered_map<T1, T2>& v) {
  return os << std::map<T1, T2>(v.begin(), v.end());
}
const long long int MOD = 1e9 + 7;
const long long int INF = 1e18;
const double EPS = 1e-6;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  while (T--) {
    int n, q, m;
    cin >> n >> m;
    vector<vector<pair<long long int, int>>> g(n);
    set<pair<long long int, pair<int, int>>> bad_edges;
    for (int i = 0; i < m; ++i) {
      long long int u, v, w;
      cin >> u >> v >> w;
      --u, --v;
      g[u].emplace_back(w, v);
      g[v].emplace_back(w, u);
      if (u > v) swap(u, v);
      bad_edges.emplace(w, make_pair(u, v));
    }
    vector<vector<pair<long long int, int>>> tree(n);
    vector<bool> vis(n, false);
    vector<long long int> distree(n, -1LL), depth(n);
    const int LOGN = (int)ceil(log2(n)) + 5;
    vector<vector<int>> par(n, vector<int>(LOGN, -1));
    function<void(int, int, long long int, int)> make_tree =
        [&](int s, int pa, long long int dis, int dep) {
          vis[s] = true;
          distree[s] = dis;
          depth[s] = dep;
          par[s][0] = pa;
          vis[s] = true;
          for (int i = 1; i < LOGN; ++i)
            if (par[s][i - 1] != -1) par[s][i] = par[par[s][i - 1]][i - 1];
          for (auto d : g[s]) {
            if (vis[d.second]) continue;
            tree[s].push_back(d);
            int a = s, b = d.second;
            if (a > b) swap(a, b);
            assert(bad_edges.count(make_pair(d.first, make_pair(a, b))));
            bad_edges.erase(make_pair(d.first, make_pair(a, b)));
            make_tree(d.second, s, dis + d.first, dep + 1);
          }
        };
    make_tree(0, -1, 0, 0);
    function<int(int, int)> lca = [&](int a, int b) {
      if (depth[b] < depth[a]) swap(a, b);
      for (int i = LOGN - 1; i >= 0; --i)
        if (par[b][i] != -1 && depth[par[b][i]] >= depth[a]) b = par[b][i];
      assert(depth[a] == depth[b]);
      if (a == b) return a;
      for (int i = LOGN - 1; i >= 0; --i)
        if (par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
      assert(par[a][0] == par[b][0]);
      return par[a][0];
    };
    vector<vector<long long int>> disdij(n);
    function<void(int)> make_dij = [&](int s) {
      if (!disdij[s].empty()) return;
      disdij[s] = vector<long long int>(n, INF);
      set<pair<long long int, int>> pq;
      disdij[s][s] = 0LL;
      pq.insert({0LL, s});
      while (!pq.empty()) {
        int v;
        long long int w;
        tie(w, v) = *pq.begin();
        pq.erase(pq.begin());
        for (auto e : g[v]) {
          if (w + e.first < disdij[s][e.second]) {
            pq.erase({disdij[s][e.second], e.second});
            disdij[s][e.second] = w + e.first;
            pq.emplace(disdij[s][e.second], e.second);
          }
        }
      }
    };
    for (auto& pe : bad_edges) {
      auto e = pe.second;
      make_dij(e.first);
      make_dij(e.second);
    }
    assert(m - bad_edges.size() == n - 1);
    cin >> q;
    while (q--) {
      int u, v;
      cin >> u >> v;
      u--, v--;
      long long int ans = distree[u] + distree[v] - 2LL * distree[lca(u, v)];
      for (auto& pe : bad_edges) {
        auto e = pe.second;
        ans = min(ans, disdij[e.first][u] + disdij[e.first][v]);
        ans = min(ans, disdij[e.second][u] + disdij[e.second][v]);
      }
      cout << ans << "\n";
    }
  }
  return 0;
}

### Prompt

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

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;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << a << "\n";
  err(++it, args...);
}
template <class T1, class T2, class T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple() : a(T1()), b(T2()), c(T3()){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <class T1, class T2, class T3>
bool operator<(const triple<T1, T2, T3>& t1, const triple<T1, T2, T3>& t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else if (t1.b != t2.b)
    return t1.b < t2.b;
  else
    return t1.c < t2.c;
}
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  return os << "(" << p.first << ": " << p.second << ")";
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  bool first = true;
  os << "[";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::set<T>& v) {
  bool first = true;
  os << "{";
  for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "}";
}
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os, const std::map<T1, T2>& v) {
  bool first = true;
  os << "{";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "}";
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os,
                                const std::unordered_set<T>& v) {
  return os << std::set<T>(v.begin(), v.end());
}
template <typename T1, typename T2>
inline std::ostream& operator<<(std::ostream& os,
                                const std::unordered_map<T1, T2>& v) {
  return os << std::map<T1, T2>(v.begin(), v.end());
}
const long long int MOD = 1e9 + 7;
const long long int INF = 1e18;
const double EPS = 1e-6;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  while (T--) {
    int n, q, m;
    cin >> n >> m;
    vector<vector<pair<long long int, int>>> g(n);
    set<pair<long long int, pair<int, int>>> bad_edges;
    for (int i = 0; i < m; ++i) {
      long long int u, v, w;
      cin >> u >> v >> w;
      --u, --v;
      g[u].emplace_back(w, v);
      g[v].emplace_back(w, u);
      if (u > v) swap(u, v);
      bad_edges.emplace(w, make_pair(u, v));
    }
    vector<vector<pair<long long int, int>>> tree(n);
    vector<bool> vis(n, false);
    vector<long long int> distree(n, -1LL), depth(n);
    const int LOGN = (int)ceil(log2(n)) + 5;
    vector<vector<int>> par(n, vector<int>(LOGN, -1));
    function<void(int, int, long long int, int)> make_tree =
        [&](int s, int pa, long long int dis, int dep) {
          vis[s] = true;
          distree[s] = dis;
          depth[s] = dep;
          par[s][0] = pa;
          vis[s] = true;
          for (int i = 1; i < LOGN; ++i)
            if (par[s][i - 1] != -1) par[s][i] = par[par[s][i - 1]][i - 1];
          for (auto d : g[s]) {
            if (vis[d.second]) continue;
            tree[s].push_back(d);
            int a = s, b = d.second;
            if (a > b) swap(a, b);
            assert(bad_edges.count(make_pair(d.first, make_pair(a, b))));
            bad_edges.erase(make_pair(d.first, make_pair(a, b)));
            make_tree(d.second, s, dis + d.first, dep + 1);
          }
        };
    make_tree(0, -1, 0, 0);
    function<int(int, int)> lca = [&](int a, int b) {
      if (depth[b] < depth[a]) swap(a, b);
      for (int i = LOGN - 1; i >= 0; --i)
        if (par[b][i] != -1 && depth[par[b][i]] >= depth[a]) b = par[b][i];
      assert(depth[a] == depth[b]);
      if (a == b) return a;
      for (int i = LOGN - 1; i >= 0; --i)
        if (par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
      assert(par[a][0] == par[b][0]);
      return par[a][0];
    };
    vector<vector<long long int>> disdij(n);
    function<void(int)> make_dij = [&](int s) {
      if (!disdij[s].empty()) return;
      disdij[s] = vector<long long int>(n, INF);
      set<pair<long long int, int>> pq;
      disdij[s][s] = 0LL;
      pq.insert({0LL, s});
      while (!pq.empty()) {
        int v;
        long long int w;
        tie(w, v) = *pq.begin();
        pq.erase(pq.begin());
        for (auto e : g[v]) {
          if (w + e.first < disdij[s][e.second]) {
            pq.erase({disdij[s][e.second], e.second});
            disdij[s][e.second] = w + e.first;
            pq.emplace(disdij[s][e.second], e.second);
          }
        }
      }
    };
    for (auto& pe : bad_edges) {
      auto e = pe.second;
      make_dij(e.first);
      make_dij(e.second);
    }
    assert(m - bad_edges.size() == n - 1);
    cin >> q;
    while (q--) {
      int u, v;
      cin >> u >> v;
      u--, v--;
      long long int ans = distree[u] + distree[v] - 2LL * distree[lca(u, v)];
      for (auto& pe : bad_edges) {
        auto e = pe.second;
        ans = min(ans, disdij[e.first][u] + disdij[e.first][v]);
        ans = min(ans, disdij[e.second][u] + disdij[e.second][v]);
      }
      cout << ans << "\n";
    }
  }
  return 0;
}

```