#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1000000007;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double pi = acosl(-1.), eps = 1e-9;
inline int power(int a, int b, int m = mod, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
const int NN = 100010, MM = 220000;
int head[NN], nxt[MM], to[MM], wei[MM];
int E;
void init(int n) {
  E = 0;
  for (int i = 0; i <= n; i++) head[i] = -1;
}
void add(int u, int v, int w) {
  nxt[E] = head[u];
  to[E] = v;
  wei[E] = w;
  head[u] = E++;
  nxt[E] = head[v];
  to[E] = u;
  wei[E] = w;
  head[v] = E++;
}
int vst[NN], flag[MM];
long long rdis[NN];
int p[NN][20], deep[NN];
struct LCA {
  void dfs(int u, int fa = 0) {
    vst[u] = 1;
    p[u][0] = fa;
    deep[u] = deep[fa] + 1;
    for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i - 1]][i - 1];
    for (int e = head[u]; e != -1; e = nxt[e]) {
      int v = to[e];
      if (v == fa) continue;
      if (vst[v]) continue;
      flag[e] = 1;
      flag[e ^ 1] = 1;
      rdis[v] = rdis[u] + wei[e];
      dfs(v, u);
    }
  }
  int k_th(int u, int k) {
    for (int i = 0; i < 20; i++) {
      if (k & (1 << i)) u = p[u][i];
    }
    return u;
  }
  int lca(int a, int b) {
    if (deep[a] > deep[b]) swap(a, b);
    b = k_th(b, deep[b] - deep[a]);
    if (a == b) return a;
    for (int i = 20; i--;) {
      if (p[a][0] == p[b][0]) break;
      if (p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
    }
    return p[a][0];
  }
} lca;
int arr[NN], an;
long long dis[44][NN];
int main() {
  int n, m;
  cin >> n >> m;
  init(n);
  for (int i = 0, u, v, w; i < m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);
  }
  lca.dfs(1);
  for (int i = 0; i < E; i += 2) {
    if (!flag[i]) {
      arr[an++] = to[i];
      arr[an++] = to[i ^ 1];
    }
  }
  sort(arr, arr + an);
  an = unique(arr, arr + an) - arr;
  for (int i = 0; i < an; i++) {
    int src = arr[i];
    for (int j = 1; j <= n; j++) dis[i][j] = INF;
    dis[i][arr[i]] = 0;
    queue<int> q;
    q.push(arr[i]);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int e = head[u]; ~e; e = nxt[e]) {
        int v = to[e];
        if (dis[i][v] > dis[i][u] + wei[e]) {
          dis[i][v] = dis[i][u] + wei[e];
          q.push(v);
        }
      }
    }
  }
  int q;
  cin >> q;
  long long ans;
  for (int u, v, w; q--;) {
    scanf("%d%d", &u, &v);
    w = lca.lca(u, v);
    ans = rdis[u] + rdis[v] - 2 * rdis[w];
    for (int i = 0; i < an; i++) {
      ans = min(ans, dis[i][u] + dis[i][v]);
    }
    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 int inf = 0x3f3f3f3f, mod = 1000000007;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double pi = acosl(-1.), eps = 1e-9;
inline int power(int a, int b, int m = mod, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
const int NN = 100010, MM = 220000;
int head[NN], nxt[MM], to[MM], wei[MM];
int E;
void init(int n) {
  E = 0;
  for (int i = 0; i <= n; i++) head[i] = -1;
}
void add(int u, int v, int w) {
  nxt[E] = head[u];
  to[E] = v;
  wei[E] = w;
  head[u] = E++;
  nxt[E] = head[v];
  to[E] = u;
  wei[E] = w;
  head[v] = E++;
}
int vst[NN], flag[MM];
long long rdis[NN];
int p[NN][20], deep[NN];
struct LCA {
  void dfs(int u, int fa = 0) {
    vst[u] = 1;
    p[u][0] = fa;
    deep[u] = deep[fa] + 1;
    for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i - 1]][i - 1];
    for (int e = head[u]; e != -1; e = nxt[e]) {
      int v = to[e];
      if (v == fa) continue;
      if (vst[v]) continue;
      flag[e] = 1;
      flag[e ^ 1] = 1;
      rdis[v] = rdis[u] + wei[e];
      dfs(v, u);
    }
  }
  int k_th(int u, int k) {
    for (int i = 0; i < 20; i++) {
      if (k & (1 << i)) u = p[u][i];
    }
    return u;
  }
  int lca(int a, int b) {
    if (deep[a] > deep[b]) swap(a, b);
    b = k_th(b, deep[b] - deep[a]);
    if (a == b) return a;
    for (int i = 20; i--;) {
      if (p[a][0] == p[b][0]) break;
      if (p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
    }
    return p[a][0];
  }
} lca;
int arr[NN], an;
long long dis[44][NN];
int main() {
  int n, m;
  cin >> n >> m;
  init(n);
  for (int i = 0, u, v, w; i < m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);
  }
  lca.dfs(1);
  for (int i = 0; i < E; i += 2) {
    if (!flag[i]) {
      arr[an++] = to[i];
      arr[an++] = to[i ^ 1];
    }
  }
  sort(arr, arr + an);
  an = unique(arr, arr + an) - arr;
  for (int i = 0; i < an; i++) {
    int src = arr[i];
    for (int j = 1; j <= n; j++) dis[i][j] = INF;
    dis[i][arr[i]] = 0;
    queue<int> q;
    q.push(arr[i]);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int e = head[u]; ~e; e = nxt[e]) {
        int v = to[e];
        if (dis[i][v] > dis[i][u] + wei[e]) {
          dis[i][v] = dis[i][u] + wei[e];
          q.push(v);
        }
      }
    }
  }
  int q;
  cin >> q;
  long long ans;
  for (int u, v, w; q--;) {
    scanf("%d%d", &u, &v);
    w = lca.lca(u, v);
    ans = rdis[u] + rdis[v] - 2 * rdis[w];
    for (int i = 0; i < an; i++) {
      ans = min(ans, dis[i][u] + dis[i][v]);
    }
    printf("%I64d\n", ans);
  }
  return 0;
}

```