#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e16;
int n, m, Q, d[100010], fa[100010][25], used[100010], a[45], k;
long long dis[45][100010], f[100010];
bool vis[100010];
int cnt, head[100010], to[200010], nxt[200010], w[200010];
priority_queue<pair<long long, int> > q;
void add(int first, int second, int z) {
  cnt++;
  to[cnt] = second;
  nxt[cnt] = head[first];
  head[first] = cnt;
  w[cnt] = z;
}
void dfs(int first) {
  vis[first] = true;
  for (int i = head[first]; i; i = nxt[i]) {
    int second = to[i];
    if (second == fa[first][0]) {
      continue;
    }
    if (vis[second]) {
      if (!used[first]) {
        a[++k] = first;
        used[first] = k;
      }
      if (!used[second]) {
        a[++k] = second;
        used[second] = k;
      }
      continue;
    }
    d[second] = d[first] + 1;
    f[second] = f[first] + w[i];
    fa[second][0] = first;
    dfs(second);
  }
}
void bz() {
  for (int i = 1; i <= 20; i++) {
    for (int j = 1; j <= n; j++) {
      fa[j][i] = fa[fa[j][i - 1]][i - 1];
    }
  }
}
int lca(int first, int second) {
  if (d[first] < d[second]) {
    swap(first, second);
  }
  int dist = d[first] - d[second];
  for (int i = 20; i >= 0; i--) {
    if (dist & (1 << i)) {
      first = fa[first][i];
    }
  }
  if (first == second) {
    return first;
  }
  for (int i = 20; i >= 0; i--) {
    if (fa[first][i] != fa[second][i]) {
      first = fa[first][i];
      second = fa[second][i];
    }
  }
  return fa[first][0];
}
void dij(int t) {
  for (int i = 1; i <= n; i++) {
    dis[t][i] = inf;
    vis[i] = false;
  }
  dis[t][a[t]] = 0;
  q.push(make_pair(0, a[t]));
  while (!q.empty()) {
    int first = q.top().second;
    q.pop();
    if (vis[first]) {
      continue;
    }
    vis[first] = true;
    for (int i = head[first]; i; i = nxt[i]) {
      int second = to[i];
      if (vis[second]) {
        continue;
      }
      if (dis[t][second] > dis[t][first] + w[i]) {
        dis[t][second] = dis[t][first] + w[i];
        q.push(make_pair(-dis[t][second], second));
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int first, second, z;
    scanf("%d%d%d", &first, &second, &z);
    add(first, second, z);
    add(second, first, z);
  }
  d[1] = 1;
  dfs(1);
  bz();
  for (int i = 1; i <= k; i++) {
    dij(i);
  }
  scanf("%d", &Q);
  while (Q--) {
    int first, second;
    scanf("%d%d", &first, &second);
    int g = lca(first, second);
    long long ans = f[first] - f[g] + f[second] - f[g];
    for (int i = 1; i <= k; i++) {
      ans = min(ans, dis[i][first] + dis[i][second]);
    }
    printf("%I64d\n", ans);
  }
  return 0;
}

### 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;
const long long inf = 1e16;
int n, m, Q, d[100010], fa[100010][25], used[100010], a[45], k;
long long dis[45][100010], f[100010];
bool vis[100010];
int cnt, head[100010], to[200010], nxt[200010], w[200010];
priority_queue<pair<long long, int> > q;
void add(int first, int second, int z) {
  cnt++;
  to[cnt] = second;
  nxt[cnt] = head[first];
  head[first] = cnt;
  w[cnt] = z;
}
void dfs(int first) {
  vis[first] = true;
  for (int i = head[first]; i; i = nxt[i]) {
    int second = to[i];
    if (second == fa[first][0]) {
      continue;
    }
    if (vis[second]) {
      if (!used[first]) {
        a[++k] = first;
        used[first] = k;
      }
      if (!used[second]) {
        a[++k] = second;
        used[second] = k;
      }
      continue;
    }
    d[second] = d[first] + 1;
    f[second] = f[first] + w[i];
    fa[second][0] = first;
    dfs(second);
  }
}
void bz() {
  for (int i = 1; i <= 20; i++) {
    for (int j = 1; j <= n; j++) {
      fa[j][i] = fa[fa[j][i - 1]][i - 1];
    }
  }
}
int lca(int first, int second) {
  if (d[first] < d[second]) {
    swap(first, second);
  }
  int dist = d[first] - d[second];
  for (int i = 20; i >= 0; i--) {
    if (dist & (1 << i)) {
      first = fa[first][i];
    }
  }
  if (first == second) {
    return first;
  }
  for (int i = 20; i >= 0; i--) {
    if (fa[first][i] != fa[second][i]) {
      first = fa[first][i];
      second = fa[second][i];
    }
  }
  return fa[first][0];
}
void dij(int t) {
  for (int i = 1; i <= n; i++) {
    dis[t][i] = inf;
    vis[i] = false;
  }
  dis[t][a[t]] = 0;
  q.push(make_pair(0, a[t]));
  while (!q.empty()) {
    int first = q.top().second;
    q.pop();
    if (vis[first]) {
      continue;
    }
    vis[first] = true;
    for (int i = head[first]; i; i = nxt[i]) {
      int second = to[i];
      if (vis[second]) {
        continue;
      }
      if (dis[t][second] > dis[t][first] + w[i]) {
        dis[t][second] = dis[t][first] + w[i];
        q.push(make_pair(-dis[t][second], second));
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int first, second, z;
    scanf("%d%d%d", &first, &second, &z);
    add(first, second, z);
    add(second, first, z);
  }
  d[1] = 1;
  dfs(1);
  bz();
  for (int i = 1; i <= k; i++) {
    dij(i);
  }
  scanf("%d", &Q);
  while (Q--) {
    int first, second;
    scanf("%d%d", &first, &second);
    int g = lca(first, second);
    long long ans = f[first] - f[g] + f[second] - f[g];
    for (int i = 1; i <= k; i++) {
      ans = min(ans, dis[i][first] + dis[i][second]);
    }
    printf("%I64d\n", ans);
  }
  return 0;
}

```