#include <bits/stdc++.h>
using namespace std;
const int SZ = 200010;
const long long INF = 1e18 + 10;
const int mod = 1e9 + 7;
long long read() {
  long long n = 0;
  char a = getchar();
  bool flag = 0;
  while (a > '9' || a < '0') {
    if (a == '-') flag = 1;
    a = getchar();
  }
  while (a <= '9' && a >= '0') {
    n = n * 10 + a - '0', a = getchar();
  }
  if (flag) n = -n;
  return n;
}
int n, m;
struct edge {
  int t, w;
};
vector<edge> g[SZ];
void build(int f, int t, int w) { g[f].push_back((edge){t, w}); }
long long dist[44][SZ];
bool vis[44][SZ];
struct Heap {
  int u;
  long long d;
};
bool operator<(Heap a, Heap b) { return a.d > b.d; }
priority_queue<Heap> q;
void dij(int s, long long dist[], bool vis[]) {
  for (int i = 1; i <= n; i++) dist[i] = INF;
  dist[s] = 0;
  q.push((Heap){s, 0});
  while (q.size()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i].t;
      if (dist[v] > dist[u] + g[u][i].w) {
        dist[v] = dist[u] + g[u][i].w;
        q.push((Heap){v, dist[v]});
      }
    }
  }
}
int fa[SZ];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int deep[SZ];
int anc[SZ][22];
long long dis[SZ];
int lg[SZ];
void dfsLca(int u, int f) {
  anc[u][0] = f;
  deep[u] = deep[f] + 1;
  for (int i = 1; i <= lg[deep[u]]; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].t;
    if (v == f) continue;
    dis[v] = dis[u] + g[u][i].w;
    dfsLca(v, u);
  }
}
int askLca(int u, int v) {
  if (deep[u] < deep[v]) swap(u, v);
  int dd = deep[u] - deep[v];
  for (int i = lg[n]; i >= 0; i--)
    if (dd & (1 << i)) u = anc[u][i];
  if (u == v) return u;
  for (int i = lg[n]; i >= 0; i--)
    if (anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
  return anc[u][0];
}
long long ask_dist(int u, int v) {
  return dis[u] + dis[v] - 2 * dis[askLca(u, v)];
}
struct haha {
  int f, t, w;
} l[SZ];
bool use[SZ];
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) lg[i] = log2(i);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &l[i].f, &l[i].t, &l[i].w);
  for (int i = 1; i <= n; i++) fa[i] = i;
  for (int i = 1; i <= m; i++) {
    int x = find(l[i].f);
    int y = find(l[i].t);
    if (x != y) {
      build(l[i].f, l[i].t, l[i].w);
      build(l[i].t, l[i].f, l[i].w);
      fa[x] = y;
      use[i] = 1;
    }
  }
  dfsLca(1, 0);
  for (int i = 1; i <= m; i++) {
    if (!use[i]) {
      build(l[i].f, l[i].t, l[i].w);
      build(l[i].t, l[i].f, l[i].w);
    }
  }
  int k = m - n + 1;
  for (int i = 1, x = 0; i <= m; i++) {
    if (!use[i]) {
      dij(l[i].f, dist[2 * x], vis[2 * x]);
      dij(l[i].t, dist[2 * x + 1], vis[2 * x + 1]);
      x++;
    }
  }
  int q = read();
  while (q--) {
    int u = read(), v = read();
    long long ans = ask_dist(u, v);
    for (int i = 0; i < 2 * k; i++) {
      ans = min(ans, dist[i][u] + dist[i][v]);
    }
    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 SZ = 200010;
const long long INF = 1e18 + 10;
const int mod = 1e9 + 7;
long long read() {
  long long n = 0;
  char a = getchar();
  bool flag = 0;
  while (a > '9' || a < '0') {
    if (a == '-') flag = 1;
    a = getchar();
  }
  while (a <= '9' && a >= '0') {
    n = n * 10 + a - '0', a = getchar();
  }
  if (flag) n = -n;
  return n;
}
int n, m;
struct edge {
  int t, w;
};
vector<edge> g[SZ];
void build(int f, int t, int w) { g[f].push_back((edge){t, w}); }
long long dist[44][SZ];
bool vis[44][SZ];
struct Heap {
  int u;
  long long d;
};
bool operator<(Heap a, Heap b) { return a.d > b.d; }
priority_queue<Heap> q;
void dij(int s, long long dist[], bool vis[]) {
  for (int i = 1; i <= n; i++) dist[i] = INF;
  dist[s] = 0;
  q.push((Heap){s, 0});
  while (q.size()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i].t;
      if (dist[v] > dist[u] + g[u][i].w) {
        dist[v] = dist[u] + g[u][i].w;
        q.push((Heap){v, dist[v]});
      }
    }
  }
}
int fa[SZ];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int deep[SZ];
int anc[SZ][22];
long long dis[SZ];
int lg[SZ];
void dfsLca(int u, int f) {
  anc[u][0] = f;
  deep[u] = deep[f] + 1;
  for (int i = 1; i <= lg[deep[u]]; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].t;
    if (v == f) continue;
    dis[v] = dis[u] + g[u][i].w;
    dfsLca(v, u);
  }
}
int askLca(int u, int v) {
  if (deep[u] < deep[v]) swap(u, v);
  int dd = deep[u] - deep[v];
  for (int i = lg[n]; i >= 0; i--)
    if (dd & (1 << i)) u = anc[u][i];
  if (u == v) return u;
  for (int i = lg[n]; i >= 0; i--)
    if (anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
  return anc[u][0];
}
long long ask_dist(int u, int v) {
  return dis[u] + dis[v] - 2 * dis[askLca(u, v)];
}
struct haha {
  int f, t, w;
} l[SZ];
bool use[SZ];
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) lg[i] = log2(i);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &l[i].f, &l[i].t, &l[i].w);
  for (int i = 1; i <= n; i++) fa[i] = i;
  for (int i = 1; i <= m; i++) {
    int x = find(l[i].f);
    int y = find(l[i].t);
    if (x != y) {
      build(l[i].f, l[i].t, l[i].w);
      build(l[i].t, l[i].f, l[i].w);
      fa[x] = y;
      use[i] = 1;
    }
  }
  dfsLca(1, 0);
  for (int i = 1; i <= m; i++) {
    if (!use[i]) {
      build(l[i].f, l[i].t, l[i].w);
      build(l[i].t, l[i].f, l[i].w);
    }
  }
  int k = m - n + 1;
  for (int i = 1, x = 0; i <= m; i++) {
    if (!use[i]) {
      dij(l[i].f, dist[2 * x], vis[2 * x]);
      dij(l[i].t, dist[2 * x + 1], vis[2 * x + 1]);
      x++;
    }
  }
  int q = read();
  while (q--) {
    int u = read(), v = read();
    long long ans = ask_dist(u, v);
    for (int i = 0; i < 2 * k; i++) {
      ans = min(ans, dist[i][u] + dist[i][v]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

```