#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 100005, K = 23;
const ll INF = ll(1e18);
int n, m, q, cnt, ccnt, p[2 * K], sp[N][K], v[N];
vector<pii> e[N], t[N];
ll ad[2 * K][2 * K], dep[N], dp[N], d[2 * K];
void g(int x, int y) {
  v[x] = ++ccnt;
  for (pii i : e[x]) {
    if (i.first == y) continue;
    if (!v[i.first]) {
      t[x].push_back(i);
      g(i.first, x);
    } else if (v[i.first] < v[x]) {
      cnt += 2;
      p[cnt - 2] = x;
      p[cnt - 1] = i.first;
      ad[cnt - 2][cnt - 1] = ad[cnt - 1][cnt - 2] = i.second;
    }
  }
}
void f(int x, int y, int z, ll d) {
  dep[x] = d;
  dp[x] = z;
  sp[x][0] = y;
  for (int i = 1; i < K; i++) sp[x][i] = sp[sp[x][i - 1]][i - 1];
  for (pii i : t[x]) {
    if (i.first == y) continue;
    f(i.first, x, z + 1, d + i.second);
  }
}
ll l(int x, int y) {
  if (dp[x] < dp[y]) swap(x, y);
  ll dx = dep[x], dy = dep[y];
  for (int i = K - 1; i >= 0; i--) {
    if (dp[x] - (1 << i) >= dp[y]) x = sp[x][i];
  }
  if (x == y) return dx - dep[x];
  for (int i = K - 1; i >= 0; i--) {
    if (sp[x][i] != sp[y][i]) {
      x = sp[x][i];
      y = sp[y][i];
    }
  }
  return dx + dy - 2 * dep[sp[x][0]];
}
ll di(int x, int y) {
  fill(d, d + cnt, INF);
  fill(v, v + cnt, 0);
  d[x] = 0;
  for (int c = x;;) {
    if (c == y) return d[c];
    v[c] = 1;
    for (int i = 0; i < cnt; i++) d[i] = min(d[i], d[c] + ad[c][i]);
    int mi = -1;
    for (int i = 0; i < cnt; i++)
      if (!v[i] && (mi == -1 || d[i] < d[mi])) {
        mi = i;
      }
    c = mi;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0, x, y, z; i < m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    e[x].push_back({y, z});
    e[y].push_back({x, z});
  }
  for (int i = 0; i < 2 * K; i++) {
    fill(ad[i], ad[i] + 2 * K, INF);
    ad[i][i] = 0;
  }
  g(1, 0);
  f(1, 0, 0, 0);
  for (int i = 0; i < cnt; i++) {
    for (int j = i + 1; j < cnt; j++) {
      ad[i][j] = ad[j][i] = min(ad[i][j], l(p[i], p[j]));
    }
  }
  scanf("%d", &q);
  cnt += 2;
  for (int x, y; q--;) {
    scanf("%d%d", &x, &y);
    p[cnt - 2] = x;
    p[cnt - 1] = y;
    for (int i = 0; i < cnt - 2; i++) {
      ad[i][cnt - 2] = ad[cnt - 2][i] = l(p[i], x);
      ad[i][cnt - 1] = ad[cnt - 1][i] = l(p[i], y);
    }
    ad[cnt - 2][cnt - 1] = ad[cnt - 1][cnt - 2] = l(x, y);
    printf("%lld\n", di(cnt - 2, cnt - 1));
  }
}

### Prompt

Develop a solution in Cpp 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;
using ll = long long;
using pii = pair<int, int>;
const int N = 100005, K = 23;
const ll INF = ll(1e18);
int n, m, q, cnt, ccnt, p[2 * K], sp[N][K], v[N];
vector<pii> e[N], t[N];
ll ad[2 * K][2 * K], dep[N], dp[N], d[2 * K];
void g(int x, int y) {
  v[x] = ++ccnt;
  for (pii i : e[x]) {
    if (i.first == y) continue;
    if (!v[i.first]) {
      t[x].push_back(i);
      g(i.first, x);
    } else if (v[i.first] < v[x]) {
      cnt += 2;
      p[cnt - 2] = x;
      p[cnt - 1] = i.first;
      ad[cnt - 2][cnt - 1] = ad[cnt - 1][cnt - 2] = i.second;
    }
  }
}
void f(int x, int y, int z, ll d) {
  dep[x] = d;
  dp[x] = z;
  sp[x][0] = y;
  for (int i = 1; i < K; i++) sp[x][i] = sp[sp[x][i - 1]][i - 1];
  for (pii i : t[x]) {
    if (i.first == y) continue;
    f(i.first, x, z + 1, d + i.second);
  }
}
ll l(int x, int y) {
  if (dp[x] < dp[y]) swap(x, y);
  ll dx = dep[x], dy = dep[y];
  for (int i = K - 1; i >= 0; i--) {
    if (dp[x] - (1 << i) >= dp[y]) x = sp[x][i];
  }
  if (x == y) return dx - dep[x];
  for (int i = K - 1; i >= 0; i--) {
    if (sp[x][i] != sp[y][i]) {
      x = sp[x][i];
      y = sp[y][i];
    }
  }
  return dx + dy - 2 * dep[sp[x][0]];
}
ll di(int x, int y) {
  fill(d, d + cnt, INF);
  fill(v, v + cnt, 0);
  d[x] = 0;
  for (int c = x;;) {
    if (c == y) return d[c];
    v[c] = 1;
    for (int i = 0; i < cnt; i++) d[i] = min(d[i], d[c] + ad[c][i]);
    int mi = -1;
    for (int i = 0; i < cnt; i++)
      if (!v[i] && (mi == -1 || d[i] < d[mi])) {
        mi = i;
      }
    c = mi;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0, x, y, z; i < m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    e[x].push_back({y, z});
    e[y].push_back({x, z});
  }
  for (int i = 0; i < 2 * K; i++) {
    fill(ad[i], ad[i] + 2 * K, INF);
    ad[i][i] = 0;
  }
  g(1, 0);
  f(1, 0, 0, 0);
  for (int i = 0; i < cnt; i++) {
    for (int j = i + 1; j < cnt; j++) {
      ad[i][j] = ad[j][i] = min(ad[i][j], l(p[i], p[j]));
    }
  }
  scanf("%d", &q);
  cnt += 2;
  for (int x, y; q--;) {
    scanf("%d%d", &x, &y);
    p[cnt - 2] = x;
    p[cnt - 1] = y;
    for (int i = 0; i < cnt - 2; i++) {
      ad[i][cnt - 2] = ad[cnt - 2][i] = l(p[i], x);
      ad[i][cnt - 1] = ad[cnt - 1][i] = l(p[i], y);
    }
    ad[cnt - 2][cnt - 1] = ad[cnt - 1][cnt - 2] = l(x, y);
    printf("%lld\n", di(cnt - 2, cnt - 1));
  }
}

```