#include <bits/stdc++.h>
using namespace std;
typedef struct {
  long long to, nxt, in;
  long long w;
} edge;
edge e[200051];
long long cnt, head[100051], eu[200051], vis[100051], f[200051][30],
    notree[101], first[100051];
long long dep[100051], dis[101][100051], ans, c;
long long i, j, n, m, q, x, y, cnt1, cnt2, o, a, b;
long long fa[100051];
queue<long long> q1;
long long find(long long x) {
  if (fa[x] == -1) return x;
  fa[x] = find(fa[x]);
  return fa[x];
}
void add(long long a, long long b, long long c) {
  cnt++;
  e[cnt].to = b;
  e[cnt].nxt = head[a];
  e[cnt].w = c;
  head[a] = cnt;
}
void dfs(long long o, long long deep, long long faa) {
  dep[o] = deep;
  fa[o] = faa;
  for (int i = head[o]; i != -1; i = e[i].nxt) {
    int v = e[i].to;
    long long w1 = e[i].w;
    if (vis[v] == 0) {
      eu[++cnt1] = v;
      e[i].in = 1;
      vis[v] = 1;
      dfs(v, deep + w1, o);
      eu[++cnt1] = o;
    } else if (vis[v] == 1 && v != faa) {
      notree[++cnt2] = v;
      notree[++cnt2] = o;
    }
  }
}
void ST() {
  for (int i = 1; i <= cnt1; i++)
    if (first[eu[i]] == 0) first[eu[i]] = i;
  for (int i = 1; i <= cnt1; i++) f[i][0] = eu[i];
  for (int j = 1; (1 << j) <= cnt1; j++)
    for (int i = 1; i + (1 << j) - 1 <= cnt1; i++) {
      int a1 = f[i][j - 1], b1 = f[i + (1 << (j - 1))][j - 1];
      if (dep[a1] < dep[b1])
        f[i][j] = a1;
      else
        f[i][j] = b1;
    }
}
long long RMQ(long long l, long long r) {
  long long k = 0;
  while ((1 << (k + 1)) <= (r - l + 1)) k++;
  int a1 = f[l][k];
  int b1 = f[r - (1 << k) + 1][k];
  if (dep[a1] < dep[b1])
    return a1;
  else
    return b1;
}
long long LCA(int a, int b) {
  if (first[a] > first[b]) swap(a, b);
  long long res = RMQ(first[a], first[b]);
  return res;
}
void spfa(int s, int loc) {
  q1.push(s);
  dis[loc][s] = 0;
  while (!q1.empty()) {
    o = q1.front();
    q1.pop();
    vis[o] = 1;
    for (int i = head[o]; i != -1; i = e[i].nxt) {
      int v = e[i].to;
      long long ww = e[i].w;
      if (dis[loc][o] + ww < dis[loc][v]) {
        dis[loc][v] = dis[loc][o] + ww;
        if (vis[v] == 0) {
          vis[v] = 1;
          q1.push(v);
        }
      }
    }
    vis[o] = 0;
  }
}
int main() {
  memset(head, -1, sizeof(head));
  memset(fa, -1, sizeof(fa));
  scanf("%I64d%I64d", &n, &m);
  int a1, b1;
  for (i = 1; i <= m; i++) {
    scanf("%d%d%I64d", &a, &b, &c);
    add(a, b, c);
    add(b, a, c);
    a1 = find(a);
    b1 = find(b);
  }
  memset(vis, 0, sizeof(vis));
  vis[1] = 1;
  eu[++cnt1] = 1;
  dfs(1, 0, 0);
  ST();
  memset(vis, 0, sizeof(vis));
  memset(dis, 0X3f, sizeof(dis));
  for (i = 1; i <= cnt2; i++) {
    memset(vis, 0, sizeof(vis));
    spfa(notree[i], i);
  }
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    scanf("%d%d", &x, &y);
    ans = dep[x] + dep[y] - 2 * dep[LCA(x, y)];
    for (j = 1; j <= cnt2; j++) ans = min(ans, dis[j][x] + dis[j][y]);
    printf("%I64d\n", ans);
  }
}

### 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;
typedef struct {
  long long to, nxt, in;
  long long w;
} edge;
edge e[200051];
long long cnt, head[100051], eu[200051], vis[100051], f[200051][30],
    notree[101], first[100051];
long long dep[100051], dis[101][100051], ans, c;
long long i, j, n, m, q, x, y, cnt1, cnt2, o, a, b;
long long fa[100051];
queue<long long> q1;
long long find(long long x) {
  if (fa[x] == -1) return x;
  fa[x] = find(fa[x]);
  return fa[x];
}
void add(long long a, long long b, long long c) {
  cnt++;
  e[cnt].to = b;
  e[cnt].nxt = head[a];
  e[cnt].w = c;
  head[a] = cnt;
}
void dfs(long long o, long long deep, long long faa) {
  dep[o] = deep;
  fa[o] = faa;
  for (int i = head[o]; i != -1; i = e[i].nxt) {
    int v = e[i].to;
    long long w1 = e[i].w;
    if (vis[v] == 0) {
      eu[++cnt1] = v;
      e[i].in = 1;
      vis[v] = 1;
      dfs(v, deep + w1, o);
      eu[++cnt1] = o;
    } else if (vis[v] == 1 && v != faa) {
      notree[++cnt2] = v;
      notree[++cnt2] = o;
    }
  }
}
void ST() {
  for (int i = 1; i <= cnt1; i++)
    if (first[eu[i]] == 0) first[eu[i]] = i;
  for (int i = 1; i <= cnt1; i++) f[i][0] = eu[i];
  for (int j = 1; (1 << j) <= cnt1; j++)
    for (int i = 1; i + (1 << j) - 1 <= cnt1; i++) {
      int a1 = f[i][j - 1], b1 = f[i + (1 << (j - 1))][j - 1];
      if (dep[a1] < dep[b1])
        f[i][j] = a1;
      else
        f[i][j] = b1;
    }
}
long long RMQ(long long l, long long r) {
  long long k = 0;
  while ((1 << (k + 1)) <= (r - l + 1)) k++;
  int a1 = f[l][k];
  int b1 = f[r - (1 << k) + 1][k];
  if (dep[a1] < dep[b1])
    return a1;
  else
    return b1;
}
long long LCA(int a, int b) {
  if (first[a] > first[b]) swap(a, b);
  long long res = RMQ(first[a], first[b]);
  return res;
}
void spfa(int s, int loc) {
  q1.push(s);
  dis[loc][s] = 0;
  while (!q1.empty()) {
    o = q1.front();
    q1.pop();
    vis[o] = 1;
    for (int i = head[o]; i != -1; i = e[i].nxt) {
      int v = e[i].to;
      long long ww = e[i].w;
      if (dis[loc][o] + ww < dis[loc][v]) {
        dis[loc][v] = dis[loc][o] + ww;
        if (vis[v] == 0) {
          vis[v] = 1;
          q1.push(v);
        }
      }
    }
    vis[o] = 0;
  }
}
int main() {
  memset(head, -1, sizeof(head));
  memset(fa, -1, sizeof(fa));
  scanf("%I64d%I64d", &n, &m);
  int a1, b1;
  for (i = 1; i <= m; i++) {
    scanf("%d%d%I64d", &a, &b, &c);
    add(a, b, c);
    add(b, a, c);
    a1 = find(a);
    b1 = find(b);
  }
  memset(vis, 0, sizeof(vis));
  vis[1] = 1;
  eu[++cnt1] = 1;
  dfs(1, 0, 0);
  ST();
  memset(vis, 0, sizeof(vis));
  memset(dis, 0X3f, sizeof(dis));
  for (i = 1; i <= cnt2; i++) {
    memset(vis, 0, sizeof(vis));
    spfa(notree[i], i);
  }
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    scanf("%d%d", &x, &y);
    ans = dep[x] + dep[y] - 2 * dep[LCA(x, y)];
    for (j = 1; j <= cnt2; j++) ans = min(ans, dis[j][x] + dis[j][y]);
    printf("%I64d\n", ans);
  }
}

```