#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using i3 = pair<int, ii>;
using li = pair<ll, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vli = vector<li>;
using vii = vector<ii>;
using vi3 = vector<i3>;
const int N = 1e5 + 5, L = 20;
const ll INF = 1e15;
const double eps = 1e-12, PI = acos(-1);
int n, m;
vli adj[N], Tree[N];
int to[N][L];
ll sum[N][L];
ll dis[N][25];
int dep[N];
int p[N];
ll cost[N];
ll value[25];
vi3 edges;
bool inTree[N];
int cnt = 0;
priority_queue<li, vli, greater<li> > pq;
int get(int x) { return x == p[x] ? x : p[x] = get(p[x]); }
bool join(int x, int y) {
  x = get(x);
  y = get(y);
  if (x == y) return false;
  if (rand() & 1) swap(x, y);
  p[x] = y;
  return true;
}
void djk(int u, int v) {
  dis[u][cnt] = 0;
  dis[v][cnt] = 0;
  pq.push({0, u});
  pq.push({0, v});
  while (!pq.empty()) {
    u = pq.top().second;
    ll d = pq.top().first;
    pq.pop();
    if (d != dis[u][cnt]) continue;
    for (li A : adj[u]) {
      int v = A.second;
      ll w = A.first;
      if (d + w < dis[v][cnt]) {
        dis[v][cnt] = d + w;
        pq.push({d + w, v});
      }
    }
  }
}
void dfs(int u, int p, ll c) {
  to[u][0] = p;
  sum[u][0] = c;
  dep[u] = 1 + dep[p];
  for (li T : Tree[u]) {
    int v = T.second;
    ll w = T.first;
    if (v != p) dfs(v, u, w);
  }
}
ll SUM(int u, int v) {
  if (u == v) return 0;
  ll ret = 0;
  if (dep[u] < dep[v]) swap(u, v);
  int k = dep[u] - dep[v];
  for (int i = 0; i < L; i++) {
    if (k & (1 << i)) {
      ret += sum[u][i];
      u = to[u][i];
    }
  }
  if (u == v) return ret;
  for (int i = L - 1; i >= 0; i--) {
    if (to[u][i] != to[v][i]) {
      ret += sum[u][i] + sum[v][i];
      u = to[u][i];
      v = to[v][i];
    }
  }
  return ret + sum[u][0] + sum[v][0];
}
bool cmp(i3 a, i3 b) { return a.first < b.first; }
void solve(int cs) {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v;
    ll w;
    scanf("%d %d %lld", &u, &v, &w);
    adj[u].push_back({w, v});
    adj[v].push_back({w, u});
    edges.push_back({i, {u, v}});
    cost[i] = w;
  }
  sort(edges.begin(), edges.end(), cmp);
  for (int i = 0; i < N; i++) {
    p[i] = i;
  }
  for (i3 E : edges) {
    int u = E.second.second;
    int v = E.second.first;
    int i = E.first;
    if (join(u, v)) {
      inTree[i] = true;
      Tree[u].push_back({cost[i], v});
      Tree[v].push_back({cost[i], u});
    }
  }
  for (i3 E : edges) {
    int u = E.second.second;
    int v = E.second.first;
    int i = E.first;
    if (!inTree[i]) {
      cnt++;
      value[cnt] = cost[i];
      djk(u, v);
    }
  }
  dfs(1, 0, 0);
  for (int j = 1; j < L; j++) {
    for (int i = 1; i <= n; i++) {
      to[i][j] = to[to[i][j - 1]][j - 1];
      sum[i][j] = sum[i][j - 1] + sum[to[i][j - 1]][j - 1];
    }
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int u, v;
    scanf("%d %d", &u, &v);
    ll ans = SUM(u, v);
    for (int i = 1; i <= cnt; i++) {
      ans = min(ans, dis[u][i] + dis[v][i] + value[i]);
    }
    printf("%lld\n", ans);
  }
}
int main() {
  int t = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 25; j++) {
      dis[i][j] = INF;
    }
  }
  for (int cs = 1; t--; cs++) {
    solve(cs);
  }
  return 0;
}

### Prompt

Create a solution in Cpp for 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 ii = pair<int, int>;
using i3 = pair<int, ii>;
using li = pair<ll, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vli = vector<li>;
using vii = vector<ii>;
using vi3 = vector<i3>;
const int N = 1e5 + 5, L = 20;
const ll INF = 1e15;
const double eps = 1e-12, PI = acos(-1);
int n, m;
vli adj[N], Tree[N];
int to[N][L];
ll sum[N][L];
ll dis[N][25];
int dep[N];
int p[N];
ll cost[N];
ll value[25];
vi3 edges;
bool inTree[N];
int cnt = 0;
priority_queue<li, vli, greater<li> > pq;
int get(int x) { return x == p[x] ? x : p[x] = get(p[x]); }
bool join(int x, int y) {
  x = get(x);
  y = get(y);
  if (x == y) return false;
  if (rand() & 1) swap(x, y);
  p[x] = y;
  return true;
}
void djk(int u, int v) {
  dis[u][cnt] = 0;
  dis[v][cnt] = 0;
  pq.push({0, u});
  pq.push({0, v});
  while (!pq.empty()) {
    u = pq.top().second;
    ll d = pq.top().first;
    pq.pop();
    if (d != dis[u][cnt]) continue;
    for (li A : adj[u]) {
      int v = A.second;
      ll w = A.first;
      if (d + w < dis[v][cnt]) {
        dis[v][cnt] = d + w;
        pq.push({d + w, v});
      }
    }
  }
}
void dfs(int u, int p, ll c) {
  to[u][0] = p;
  sum[u][0] = c;
  dep[u] = 1 + dep[p];
  for (li T : Tree[u]) {
    int v = T.second;
    ll w = T.first;
    if (v != p) dfs(v, u, w);
  }
}
ll SUM(int u, int v) {
  if (u == v) return 0;
  ll ret = 0;
  if (dep[u] < dep[v]) swap(u, v);
  int k = dep[u] - dep[v];
  for (int i = 0; i < L; i++) {
    if (k & (1 << i)) {
      ret += sum[u][i];
      u = to[u][i];
    }
  }
  if (u == v) return ret;
  for (int i = L - 1; i >= 0; i--) {
    if (to[u][i] != to[v][i]) {
      ret += sum[u][i] + sum[v][i];
      u = to[u][i];
      v = to[v][i];
    }
  }
  return ret + sum[u][0] + sum[v][0];
}
bool cmp(i3 a, i3 b) { return a.first < b.first; }
void solve(int cs) {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v;
    ll w;
    scanf("%d %d %lld", &u, &v, &w);
    adj[u].push_back({w, v});
    adj[v].push_back({w, u});
    edges.push_back({i, {u, v}});
    cost[i] = w;
  }
  sort(edges.begin(), edges.end(), cmp);
  for (int i = 0; i < N; i++) {
    p[i] = i;
  }
  for (i3 E : edges) {
    int u = E.second.second;
    int v = E.second.first;
    int i = E.first;
    if (join(u, v)) {
      inTree[i] = true;
      Tree[u].push_back({cost[i], v});
      Tree[v].push_back({cost[i], u});
    }
  }
  for (i3 E : edges) {
    int u = E.second.second;
    int v = E.second.first;
    int i = E.first;
    if (!inTree[i]) {
      cnt++;
      value[cnt] = cost[i];
      djk(u, v);
    }
  }
  dfs(1, 0, 0);
  for (int j = 1; j < L; j++) {
    for (int i = 1; i <= n; i++) {
      to[i][j] = to[to[i][j - 1]][j - 1];
      sum[i][j] = sum[i][j - 1] + sum[to[i][j - 1]][j - 1];
    }
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int u, v;
    scanf("%d %d", &u, &v);
    ll ans = SUM(u, v);
    for (int i = 1; i <= cnt; i++) {
      ans = min(ans, dis[u][i] + dis[v][i] + value[i]);
    }
    printf("%lld\n", ans);
  }
}
int main() {
  int t = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 25; j++) {
      dis[i][j] = INF;
    }
  }
  for (int cs = 1; t--; cs++) {
    solve(cs);
  }
  return 0;
}

```