#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node {
  int v, nxt, d, s;
} p[N << 2];
int head[N], vis[N], hd, tot;
long long dis[25][N];
void init() {
  tot = 0;
  memset(head, -1, sizeof(head));
  memset(dis, 0x3f, sizeof(dis));
}
void add(int x, int y, int d) {
  p[tot].v = y;
  p[tot].d = d;
  p[tot].nxt = head[x];
  head[x] = tot++;
}
void spt(int x) {
  vis[x] = 1;
  for (int i = head[x]; ~i; i = p[i].nxt) {
    int y = p[i].v;
    if (vis[y]) continue;
    p[i].s = p[i ^ 1].s = 1;
    spt(y);
  }
}
priority_queue<pair<long long, int> > q;
void dij(int s, long long *dis) {
  dis[s] = 0;
  q.push(make_pair(0, s));
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    for (int i = head[x]; ~i; i = p[i].nxt) {
      int y = p[i].v;
      if (dis[y] > dis[x] + p[i].d) {
        dis[y] = dis[x] + p[i].d;
        q.push(make_pair(dis[y], y));
      }
    }
  }
}
int dep[N], anc[N][20];
long long dd[N];
void dfs(int x, int fa) {
  dep[x] = dep[fa] + 1;
  anc[x][0] = fa;
  for (int i = 1; i < 20; i++) {
    anc[x][i] = anc[anc[x][i - 1]][i - 1];
  }
  for (int i = head[x]; ~i; i = p[i].nxt) {
    int y = p[i].v;
    if (!p[i].s || y == fa) continue;
    dd[y] = p[i].d + dd[x];
    dfs(y, x);
  }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = 19; i >= 0; i--) {
    if (dep[anc[x][i]] >= dep[y]) {
      x = anc[x][i];
    }
  }
  if (x == y) return x;
  for (int i = 19; i >= 0; i--) {
    if (anc[x][i] != anc[y][i]) {
      x = anc[x][i];
      y = anc[y][i];
    }
  }
  return anc[x][0];
}
int main() {
  init();
  int n, m, q, x, y, d;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &x, &y, &d);
    add(x, y, d);
    add(y, x, d);
  }
  spt(1);
  for (int i = 0; i < tot; i += 2) {
    if (!p[i].s) {
      dij(p[i].v, dis[hd++]);
    }
  }
  dfs(1, 0);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &x, &y);
    long long res = dd[x] + dd[y] - 2 * dd[lca(x, y)];
    for (int i = 0; i < hd; i++) {
      res = min(res, dis[i][x] + dis[i][y]);
    }
    printf("%lld\n", res);
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 int N = 1e5 + 5;
struct node {
  int v, nxt, d, s;
} p[N << 2];
int head[N], vis[N], hd, tot;
long long dis[25][N];
void init() {
  tot = 0;
  memset(head, -1, sizeof(head));
  memset(dis, 0x3f, sizeof(dis));
}
void add(int x, int y, int d) {
  p[tot].v = y;
  p[tot].d = d;
  p[tot].nxt = head[x];
  head[x] = tot++;
}
void spt(int x) {
  vis[x] = 1;
  for (int i = head[x]; ~i; i = p[i].nxt) {
    int y = p[i].v;
    if (vis[y]) continue;
    p[i].s = p[i ^ 1].s = 1;
    spt(y);
  }
}
priority_queue<pair<long long, int> > q;
void dij(int s, long long *dis) {
  dis[s] = 0;
  q.push(make_pair(0, s));
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    for (int i = head[x]; ~i; i = p[i].nxt) {
      int y = p[i].v;
      if (dis[y] > dis[x] + p[i].d) {
        dis[y] = dis[x] + p[i].d;
        q.push(make_pair(dis[y], y));
      }
    }
  }
}
int dep[N], anc[N][20];
long long dd[N];
void dfs(int x, int fa) {
  dep[x] = dep[fa] + 1;
  anc[x][0] = fa;
  for (int i = 1; i < 20; i++) {
    anc[x][i] = anc[anc[x][i - 1]][i - 1];
  }
  for (int i = head[x]; ~i; i = p[i].nxt) {
    int y = p[i].v;
    if (!p[i].s || y == fa) continue;
    dd[y] = p[i].d + dd[x];
    dfs(y, x);
  }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = 19; i >= 0; i--) {
    if (dep[anc[x][i]] >= dep[y]) {
      x = anc[x][i];
    }
  }
  if (x == y) return x;
  for (int i = 19; i >= 0; i--) {
    if (anc[x][i] != anc[y][i]) {
      x = anc[x][i];
      y = anc[y][i];
    }
  }
  return anc[x][0];
}
int main() {
  init();
  int n, m, q, x, y, d;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &x, &y, &d);
    add(x, y, d);
    add(y, x, d);
  }
  spt(1);
  for (int i = 0; i < tot; i += 2) {
    if (!p[i].s) {
      dij(p[i].v, dis[hd++]);
    }
  }
  dfs(1, 0);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &x, &y);
    long long res = dd[x] + dd[y] - 2 * dd[lca(x, y)];
    for (int i = 0; i < hd; i++) {
      res = min(res, dis[i][x] + dis[i][y]);
    }
    printf("%lld\n", res);
  }
  return 0;
}

```