#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
vector<vector<int> > g;
vector<vector<int> > tree;
vector<bool> used;
map<pair<int, int>, int> edges;
vector<long long> h;
vector<int> tin, tout;
vector<vector<int> > par;
unordered_map<int, vector<long long> > D;
int timer = 0;
void bfs(int v) {
  queue<int> q;
  q.push(v);
  used[v] = 1;
  while (!q.empty()) {
    v = q.front();
    q.pop();
    for (int i = 0; i < g[v].size(); i++) {
      int to = g[v][i];
      if (!used[to]) {
        used[to] = 1;
        tree[v].push_back(to);
        tree[to].push_back(v);
        edges[{v, to}] *= -1;
        edges[{to, v}] *= -1;
        q.push(to);
      }
    }
  }
}
void init(int n) {
  int log_ = 0;
  while ((1 << log_) < n) log_++;
  for (int i = 0; i < n; i++) par[i].resize(log_ + 1);
}
void dfs(int v, int p) {
  tin[v] = timer++;
  par[v][0] = p;
  for (int i = 1; i < par[v].size(); i++) par[v][i] = par[par[v][i - 1]][i - 1];
  for (int i = 0; i < tree[v].size(); i++) {
    int to = tree[v][i];
    if (to == p) continue;
    h[to] = h[v] + edges[{v, to}];
    dfs(to, v);
  }
  tout[v] = timer++;
}
bool upper(int u, int v) { return (tin[u] <= tin[v] && tout[u] >= tout[v]); }
int lca(int u, int v) {
  if (upper(u, v)) return u;
  if (upper(v, u)) return v;
  for (int i = par[v].size() - 1; i >= 0; i--)
    if (!upper(par[v][i], u)) v = par[v][i];
  return par[v][0];
}
void D_init(int n) {
  for (auto it = edges.begin(); it != edges.end(); it++) {
    if (it->second < 0)
      it->second *= -1;
    else
      D[it->first.first].resize(n, LLONG_MAX),
          edges[{it->first.second, it->first.first}] *= -1;
  }
  for (auto it = D.begin(); it != D.end(); it++) {
    int i = it->first;
    set<pair<long long, int> > q;
    D[i][i] = 0;
    q.insert({0, i});
    while (!q.empty()) {
      int v = q.begin()->second;
      q.erase(q.begin());
      for (int j = 0; j < g[v].size(); j++) {
        int to = g[v][j];
        if (D[i][to] > D[i][v] + edges[{v, to}]) {
          q.erase({D[i][to], to});
          D[i][to] = D[i][v] + edges[{v, to}];
          q.insert({D[i][to], to});
        }
      }
    }
  }
}
long long ans(int u, int v) {
  long long mn = LLONG_MAX;
  for (auto it = D.begin(); it != D.end(); it++)
    mn = min(mn, (it->second)[u] + (it->second)[v]);
  return (min(h[u] + h[v] - 2 * h[lca(u, v)], mn));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  g.resize(n), used.resize(n), tree.resize(n), h.resize(n), par.resize(n),
      tin.resize(n), tout.resize(n);
  for (int i = 0; i < m; i++) {
    int u, v, d;
    cin >> u >> v >> d;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
    edges[{u, v}] = d;
    edges[{v, u}] = d;
  }
  bfs(0);
  D_init(n);
  init(n);
  dfs(0, 0);
  int q;
  cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    cout << ans(u, v) << '\n';
  }
  return 0;
}

### Prompt

Please create a solution in CPP 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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
vector<vector<int> > g;
vector<vector<int> > tree;
vector<bool> used;
map<pair<int, int>, int> edges;
vector<long long> h;
vector<int> tin, tout;
vector<vector<int> > par;
unordered_map<int, vector<long long> > D;
int timer = 0;
void bfs(int v) {
  queue<int> q;
  q.push(v);
  used[v] = 1;
  while (!q.empty()) {
    v = q.front();
    q.pop();
    for (int i = 0; i < g[v].size(); i++) {
      int to = g[v][i];
      if (!used[to]) {
        used[to] = 1;
        tree[v].push_back(to);
        tree[to].push_back(v);
        edges[{v, to}] *= -1;
        edges[{to, v}] *= -1;
        q.push(to);
      }
    }
  }
}
void init(int n) {
  int log_ = 0;
  while ((1 << log_) < n) log_++;
  for (int i = 0; i < n; i++) par[i].resize(log_ + 1);
}
void dfs(int v, int p) {
  tin[v] = timer++;
  par[v][0] = p;
  for (int i = 1; i < par[v].size(); i++) par[v][i] = par[par[v][i - 1]][i - 1];
  for (int i = 0; i < tree[v].size(); i++) {
    int to = tree[v][i];
    if (to == p) continue;
    h[to] = h[v] + edges[{v, to}];
    dfs(to, v);
  }
  tout[v] = timer++;
}
bool upper(int u, int v) { return (tin[u] <= tin[v] && tout[u] >= tout[v]); }
int lca(int u, int v) {
  if (upper(u, v)) return u;
  if (upper(v, u)) return v;
  for (int i = par[v].size() - 1; i >= 0; i--)
    if (!upper(par[v][i], u)) v = par[v][i];
  return par[v][0];
}
void D_init(int n) {
  for (auto it = edges.begin(); it != edges.end(); it++) {
    if (it->second < 0)
      it->second *= -1;
    else
      D[it->first.first].resize(n, LLONG_MAX),
          edges[{it->first.second, it->first.first}] *= -1;
  }
  for (auto it = D.begin(); it != D.end(); it++) {
    int i = it->first;
    set<pair<long long, int> > q;
    D[i][i] = 0;
    q.insert({0, i});
    while (!q.empty()) {
      int v = q.begin()->second;
      q.erase(q.begin());
      for (int j = 0; j < g[v].size(); j++) {
        int to = g[v][j];
        if (D[i][to] > D[i][v] + edges[{v, to}]) {
          q.erase({D[i][to], to});
          D[i][to] = D[i][v] + edges[{v, to}];
          q.insert({D[i][to], to});
        }
      }
    }
  }
}
long long ans(int u, int v) {
  long long mn = LLONG_MAX;
  for (auto it = D.begin(); it != D.end(); it++)
    mn = min(mn, (it->second)[u] + (it->second)[v]);
  return (min(h[u] + h[v] - 2 * h[lca(u, v)], mn));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  g.resize(n), used.resize(n), tree.resize(n), h.resize(n), par.resize(n),
      tin.resize(n), tout.resize(n);
  for (int i = 0; i < m; i++) {
    int u, v, d;
    cin >> u >> v >> d;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
    edges[{u, v}] = d;
    edges[{v, u}] = d;
  }
  bfs(0);
  D_init(n);
  init(n);
  dfs(0, 0);
  int q;
  cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    cout << ans(u, v) << '\n';
  }
  return 0;
}

```