#include <bits/stdc++.h>
using namespace std;
vector<int> a[100010];
vector<int> w[100010];
int Q;
pair<int, int> que[100010];
long long ans[100010];
int l[30], r[30];
long long cost[30];
int n, m, cnt;
int fat[100010];
int fa[100010][20];
long long len[100010][20];
int dep[100010];
int get_fa(int x) {
  if (fat[x] == 0) return x;
  fat[x] = get_fa(fat[x]);
  return fat[x];
}
void dfs(int x, int f) {
  dep[x] = dep[f] + 1;
  for (int i = 1; i < 20; i++) {
    fa[x][i] = fa[fa[x][i - 1]][i - 1];
    len[x][i] = len[x][i - 1] + len[fa[x][i - 1]][i - 1];
  }
  for (int i = 0; i < a[x].size(); i++) {
    int u = a[x][i];
    if (u == f) continue;
    len[u][0] = w[x][i];
    fa[u][0] = x;
    dfs(u, x);
  }
}
long long lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  long long res = 0;
  for (int i = 19; i >= 0; i--)
    if (dep[fa[u][i]] >= dep[v]) {
      res += len[u][i];
      u = fa[u][i];
    }
  if (u == v) return res;
  for (int i = 19; i >= 0; i--)
    if (fa[u][i] != fa[v][i]) {
      res = res + len[u][i] + len[v][i];
      u = fa[u][i];
      v = fa[v][i];
    }
  return res + len[u][0] + len[v][0];
}
long long distA[100010], distB[100010];
int q[100010 * 5];
int head, tail;
bool inq[100010];
void spfa(int x, int y) {
  memset(distA, -1, sizeof distA);
  memset(distB, -1, sizeof distB);
  q[1] = x;
  head = 1;
  tail = 1;
  distA[x] = 0;
  while (head <= tail) {
    int nq = q[head];
    head++;
    inq[nq] = 0;
    for (int i = 0; i < a[nq].size(); i++) {
      int u = a[nq][i];
      if (distA[u] == -1 || distA[u] > distA[nq] + w[nq][i]) {
        distA[u] = distA[nq] + w[nq][i];
        if (inq[u] == 0) {
          inq[u] = 1;
          q[++tail] = u;
        }
      }
    }
  }
  q[1] = y;
  head = 1;
  tail = 1;
  distB[y] = 0;
  while (head <= tail) {
    int nq = q[head];
    head++;
    inq[nq] = 0;
    for (int i = 0; i < a[nq].size(); i++) {
      int u = a[nq][i];
      if (distB[u] == -1 || distB[u] > distB[nq] + w[nq][i]) {
        distB[u] = distB[nq] + w[nq][i];
        if (inq[u] == 0) {
          inq[u] = 1;
          q[++tail] = u;
        }
      }
    }
  }
}
int main() {
  int u, v;
  long long val;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%lld", &u, &v, &val);
    if (get_fa(u) != get_fa(v)) {
      fat[get_fa(u)] = get_fa(v);
      a[u].push_back(v);
      a[v].push_back(u);
      w[u].push_back(val);
      w[v].push_back(val);
    } else {
      cnt++;
      l[cnt] = u;
      r[cnt] = v;
      cost[cnt] = val;
    }
  }
  dfs(1, 0);
  scanf("%d", &Q);
  for (int i = 1; i <= Q; i++) {
    scanf("%d%d", &que[i].first, &que[i].second);
    ans[i] = lca(que[i].first, que[i].second);
  }
  for (int i = 1; i <= cnt; i++) {
    a[l[i]].push_back(r[i]);
    a[r[i]].push_back(l[i]);
    w[l[i]].push_back(cost[i]);
    w[r[i]].push_back(cost[i]);
  }
  for (int i = 1; i <= cnt; i++) {
    spfa(l[i], r[i]);
    for (int j = 1; j <= Q; j++)
      ans[j] = min(ans[j], min(distA[que[j].first] + distB[que[j].second],
                               distA[que[j].second] + distB[que[j].first]) +
                               cost[i]);
  }
  for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
}

### Prompt

Please formulate a cpp solution to 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;
vector<int> a[100010];
vector<int> w[100010];
int Q;
pair<int, int> que[100010];
long long ans[100010];
int l[30], r[30];
long long cost[30];
int n, m, cnt;
int fat[100010];
int fa[100010][20];
long long len[100010][20];
int dep[100010];
int get_fa(int x) {
  if (fat[x] == 0) return x;
  fat[x] = get_fa(fat[x]);
  return fat[x];
}
void dfs(int x, int f) {
  dep[x] = dep[f] + 1;
  for (int i = 1; i < 20; i++) {
    fa[x][i] = fa[fa[x][i - 1]][i - 1];
    len[x][i] = len[x][i - 1] + len[fa[x][i - 1]][i - 1];
  }
  for (int i = 0; i < a[x].size(); i++) {
    int u = a[x][i];
    if (u == f) continue;
    len[u][0] = w[x][i];
    fa[u][0] = x;
    dfs(u, x);
  }
}
long long lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  long long res = 0;
  for (int i = 19; i >= 0; i--)
    if (dep[fa[u][i]] >= dep[v]) {
      res += len[u][i];
      u = fa[u][i];
    }
  if (u == v) return res;
  for (int i = 19; i >= 0; i--)
    if (fa[u][i] != fa[v][i]) {
      res = res + len[u][i] + len[v][i];
      u = fa[u][i];
      v = fa[v][i];
    }
  return res + len[u][0] + len[v][0];
}
long long distA[100010], distB[100010];
int q[100010 * 5];
int head, tail;
bool inq[100010];
void spfa(int x, int y) {
  memset(distA, -1, sizeof distA);
  memset(distB, -1, sizeof distB);
  q[1] = x;
  head = 1;
  tail = 1;
  distA[x] = 0;
  while (head <= tail) {
    int nq = q[head];
    head++;
    inq[nq] = 0;
    for (int i = 0; i < a[nq].size(); i++) {
      int u = a[nq][i];
      if (distA[u] == -1 || distA[u] > distA[nq] + w[nq][i]) {
        distA[u] = distA[nq] + w[nq][i];
        if (inq[u] == 0) {
          inq[u] = 1;
          q[++tail] = u;
        }
      }
    }
  }
  q[1] = y;
  head = 1;
  tail = 1;
  distB[y] = 0;
  while (head <= tail) {
    int nq = q[head];
    head++;
    inq[nq] = 0;
    for (int i = 0; i < a[nq].size(); i++) {
      int u = a[nq][i];
      if (distB[u] == -1 || distB[u] > distB[nq] + w[nq][i]) {
        distB[u] = distB[nq] + w[nq][i];
        if (inq[u] == 0) {
          inq[u] = 1;
          q[++tail] = u;
        }
      }
    }
  }
}
int main() {
  int u, v;
  long long val;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%lld", &u, &v, &val);
    if (get_fa(u) != get_fa(v)) {
      fat[get_fa(u)] = get_fa(v);
      a[u].push_back(v);
      a[v].push_back(u);
      w[u].push_back(val);
      w[v].push_back(val);
    } else {
      cnt++;
      l[cnt] = u;
      r[cnt] = v;
      cost[cnt] = val;
    }
  }
  dfs(1, 0);
  scanf("%d", &Q);
  for (int i = 1; i <= Q; i++) {
    scanf("%d%d", &que[i].first, &que[i].second);
    ans[i] = lca(que[i].first, que[i].second);
  }
  for (int i = 1; i <= cnt; i++) {
    a[l[i]].push_back(r[i]);
    a[r[i]].push_back(l[i]);
    w[l[i]].push_back(cost[i]);
    w[r[i]].push_back(cost[i]);
  }
  for (int i = 1; i <= cnt; i++) {
    spfa(l[i], r[i]);
    for (int j = 1; j <= Q; j++)
      ans[j] = min(ans[j], min(distA[que[j].first] + distB[que[j].second],
                               distA[que[j].second] + distB[que[j].first]) +
                               cost[i]);
  }
  for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
}

```