#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 50;
map<long long, long long> ma;
struct asd {
  long long from, to, next;
  long long val;
} b[maxn * 2], b2[maxn * 2], b3[maxn * 2];
long long tot = 2, head[maxn];
long long diss[50][maxn];
long long bh;
inline void ad(long long aa, long long bb, long long cc) {
  b[tot].from = aa;
  b[tot].to = bb;
  b[tot].next = head[aa];
  b[tot].val = cc;
  head[aa] = tot++;
}
long long h2[maxn], t2 = 2;
inline void ad2(long long aa, long long bb, long long cc) {
  b2[t2].from = aa;
  b2[t2].to = bb;
  b2[t2].next = h2[aa];
  b2[t2].val = cc;
  h2[aa] = t2++;
}
long long h3[maxn], t3 = 2;
inline void ad3(long long aa, long long bb, long long cc) {
  b3[t3].from = aa;
  b3[t3].to = bb;
  b3[t3].next = h3[aa];
  b3[t3].val = cc;
  h3[aa] = t3++;
}
struct jie {
  long long num;
  long long dis;
  jie(long long aa = 0, long long bb = 0) { num = aa, dis = bb; }
  bool operator<(const jie& A) const { return dis > A.dis; }
};
long long vis[maxn];
void dij(long long xx) {
  priority_queue<jie> q;
  q.push(jie(xx, 0));
  diss[ma[xx]][xx] = 0;
  memset(vis, 0, sizeof(vis));
  while (!q.empty()) {
    long long now = q.top().num;
    q.pop();
    if (vis[now]) continue;
    vis[now] = 1;
    for (long long i = head[now]; i != -1; i = b[i].next) {
      long long u = b[i].to;
      if (diss[ma[xx]][u] > b[i].val + diss[ma[xx]][now]) {
        diss[ma[xx]][u] = b[i].val + diss[ma[xx]][now];
        q.push(jie(u, diss[ma[xx]][u]));
      }
    }
  }
}
long long f[maxn][25], dep[maxn];
long long cost[maxn][25];
void dfs(long long now, long long fa, long long da) {
  dep[now] = dep[fa] + 1;
  f[now][0] = fa;
  cost[now][0] = da;
  for (long long i = 1; (1 << i) <= dep[now]; i++) {
    f[now][i] = f[f[now][i - 1]][i - 1];
    cost[now][i] = cost[now][i - 1] + cost[f[now][i - 1]][i - 1];
  }
  for (long long i = h2[now]; i != -1; i = b2[i].next) {
    long long u = b2[i].to;
    if (fa != u) dfs(u, now, b2[i].val);
  }
}
long long Lca(long long aa, long long bb) {
  if (dep[aa] > dep[bb]) swap(aa, bb);
  long long len = dep[bb] - dep[aa], k = 0;
  long long ans = 0;
  while (len) {
    if (len & 1) {
      ans += cost[bb][k];
      bb = f[bb][k];
    }
    k++, len >>= 1;
  }
  if (aa == bb) return ans;
  for (long long i = 20; i >= 0; i--) {
    if (f[aa][i] == f[bb][i]) continue;
    ans += cost[aa][i];
    ans += cost[bb][i];
    aa = f[aa][i], bb = f[bb][i];
  }
  return ans + cost[aa][0] + cost[bb][0];
}
long long zx[maxn * 2], visb[maxn * 2];
long long zhao(long long xx) {
  if (xx == zx[xx]) return xx;
  return zx[xx] = zhao(zx[xx]);
}
void bing(long long xx, long long yy) { zx[zhao(xx)] = zhao(yy); }
bool cmp(asd aa, asd bb) { return aa.val < bb.val; }
void shu() {
  sort(b3 + 2, b3 + t3, cmp);
  for (long long i = 0; i < maxn; i++) zx[i] = i;
  long long cnt = 0;
  for (long long i = 2; i < t3; i++) {
    long long x = b3[i].from, y = b3[i].to;
    if (zhao(x) != zhao(y)) {
      bing(x, y);
      ad2(x, y, b3[i].val);
      ad2(y, x, b3[i].val);
      visb[i] = visb[i ^ 1] = 1;
    } else {
      ma[x] = ++bh;
      ma[y] = ++bh;
      dij(x), dij(y);
    }
  }
}
int main() {
  memset(diss, 0x3f, sizeof(diss));
  memset(head, -1, sizeof(head));
  memset(h2, -1, sizeof(h2));
  memset(h3, -1, sizeof(h3));
  long long n, m;
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= m; i++) {
    long long aa, bb;
    long long cc;
    scanf("%lld%lld%lld", &aa, &bb, &cc);
    ad(aa, bb, cc), ad(bb, aa, cc);
    ad3(aa, bb, cc);
  }
  shu();
  dfs(1, 1, 0);
  long long q;
  scanf("%lld", &q);
  for (long long i = 1; i <= q; i++) {
    long long aa, bb;
    scanf("%d%d", &aa, &bb);
    long long ans = Lca(aa, bb);
    for (long long i = 1; i <= bh; i++) {
      ans = min(ans, diss[i][aa] + diss[i][bb]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
const int maxn = 2e5 + 50;
map<long long, long long> ma;
struct asd {
  long long from, to, next;
  long long val;
} b[maxn * 2], b2[maxn * 2], b3[maxn * 2];
long long tot = 2, head[maxn];
long long diss[50][maxn];
long long bh;
inline void ad(long long aa, long long bb, long long cc) {
  b[tot].from = aa;
  b[tot].to = bb;
  b[tot].next = head[aa];
  b[tot].val = cc;
  head[aa] = tot++;
}
long long h2[maxn], t2 = 2;
inline void ad2(long long aa, long long bb, long long cc) {
  b2[t2].from = aa;
  b2[t2].to = bb;
  b2[t2].next = h2[aa];
  b2[t2].val = cc;
  h2[aa] = t2++;
}
long long h3[maxn], t3 = 2;
inline void ad3(long long aa, long long bb, long long cc) {
  b3[t3].from = aa;
  b3[t3].to = bb;
  b3[t3].next = h3[aa];
  b3[t3].val = cc;
  h3[aa] = t3++;
}
struct jie {
  long long num;
  long long dis;
  jie(long long aa = 0, long long bb = 0) { num = aa, dis = bb; }
  bool operator<(const jie& A) const { return dis > A.dis; }
};
long long vis[maxn];
void dij(long long xx) {
  priority_queue<jie> q;
  q.push(jie(xx, 0));
  diss[ma[xx]][xx] = 0;
  memset(vis, 0, sizeof(vis));
  while (!q.empty()) {
    long long now = q.top().num;
    q.pop();
    if (vis[now]) continue;
    vis[now] = 1;
    for (long long i = head[now]; i != -1; i = b[i].next) {
      long long u = b[i].to;
      if (diss[ma[xx]][u] > b[i].val + diss[ma[xx]][now]) {
        diss[ma[xx]][u] = b[i].val + diss[ma[xx]][now];
        q.push(jie(u, diss[ma[xx]][u]));
      }
    }
  }
}
long long f[maxn][25], dep[maxn];
long long cost[maxn][25];
void dfs(long long now, long long fa, long long da) {
  dep[now] = dep[fa] + 1;
  f[now][0] = fa;
  cost[now][0] = da;
  for (long long i = 1; (1 << i) <= dep[now]; i++) {
    f[now][i] = f[f[now][i - 1]][i - 1];
    cost[now][i] = cost[now][i - 1] + cost[f[now][i - 1]][i - 1];
  }
  for (long long i = h2[now]; i != -1; i = b2[i].next) {
    long long u = b2[i].to;
    if (fa != u) dfs(u, now, b2[i].val);
  }
}
long long Lca(long long aa, long long bb) {
  if (dep[aa] > dep[bb]) swap(aa, bb);
  long long len = dep[bb] - dep[aa], k = 0;
  long long ans = 0;
  while (len) {
    if (len & 1) {
      ans += cost[bb][k];
      bb = f[bb][k];
    }
    k++, len >>= 1;
  }
  if (aa == bb) return ans;
  for (long long i = 20; i >= 0; i--) {
    if (f[aa][i] == f[bb][i]) continue;
    ans += cost[aa][i];
    ans += cost[bb][i];
    aa = f[aa][i], bb = f[bb][i];
  }
  return ans + cost[aa][0] + cost[bb][0];
}
long long zx[maxn * 2], visb[maxn * 2];
long long zhao(long long xx) {
  if (xx == zx[xx]) return xx;
  return zx[xx] = zhao(zx[xx]);
}
void bing(long long xx, long long yy) { zx[zhao(xx)] = zhao(yy); }
bool cmp(asd aa, asd bb) { return aa.val < bb.val; }
void shu() {
  sort(b3 + 2, b3 + t3, cmp);
  for (long long i = 0; i < maxn; i++) zx[i] = i;
  long long cnt = 0;
  for (long long i = 2; i < t3; i++) {
    long long x = b3[i].from, y = b3[i].to;
    if (zhao(x) != zhao(y)) {
      bing(x, y);
      ad2(x, y, b3[i].val);
      ad2(y, x, b3[i].val);
      visb[i] = visb[i ^ 1] = 1;
    } else {
      ma[x] = ++bh;
      ma[y] = ++bh;
      dij(x), dij(y);
    }
  }
}
int main() {
  memset(diss, 0x3f, sizeof(diss));
  memset(head, -1, sizeof(head));
  memset(h2, -1, sizeof(h2));
  memset(h3, -1, sizeof(h3));
  long long n, m;
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= m; i++) {
    long long aa, bb;
    long long cc;
    scanf("%lld%lld%lld", &aa, &bb, &cc);
    ad(aa, bb, cc), ad(bb, aa, cc);
    ad3(aa, bb, cc);
  }
  shu();
  dfs(1, 1, 0);
  long long q;
  scanf("%lld", &q);
  for (long long i = 1; i <= q; i++) {
    long long aa, bb;
    scanf("%d%d", &aa, &bb);
    long long ans = Lca(aa, bb);
    for (long long i = 1; i <= bh; i++) {
      ans = min(ans, diss[i][aa] + diss[i][bb]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

```