#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int M = 300100;
int n, m;
struct Edge {
  struct edge {
    int u, v, nxt;
    long long w;
  } e[M];
  int tot, hd[N];
  void init() { tot = 0, memset(hd, 0, sizeof(hd)); }
  void add(int u, int v, long long w) {
    e[++tot].u = u, e[tot].v = v, e[tot].w = w, e[tot].nxt = hd[u], hd[u] = tot;
  }
} e, e2;
bool flag[M];
bool vis[N];
vector<int> v, ee;
int id[N];
long long d[42][N];
void dfs(int u, int f) {
  vis[u] = 1;
  for (int i = e.hd[u]; i; i = e.e[i].nxt) {
    int v = e.e[i].v;
    long long w = e.e[i].w;
    if (v == f || vis[v]) continue;
    flag[i] = 1;
    e2.add(u, v, w);
    e2.add(v, u, w);
    dfs(v, u);
  }
}
int deep[N], father[N][23];
long long cost[N];
void dfs2(int u, int f) {
  father[u][0] = f;
  for (int j = 1; j <= 20; j++) father[u][j] = father[father[u][j - 1]][j - 1];
  for (int i = e2.hd[u]; i; i = e2.e[i].nxt) {
    int v = e2.e[i].v;
    long long w = e2.e[i].w;
    if (v == f) continue;
    deep[v] = deep[u] + 1;
    cost[v] = cost[u] + w;
    dfs2(v, u);
  }
}
inline int getLCA(int x, int y) {
  if (deep[x] < deep[y]) swap(x, y);
  for (int i = 20; ~i; --i)
    if (deep[father[x][i]] >= deep[y]) x = father[x][i];
  if (x == y) return x;
  for (int i = 20; ~i; --i)
    if (father[x][i] != father[y][i]) x = father[x][i], y = father[y][i];
  return father[x][0];
}
void dijkstra(int x, int id) {
  priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                 greater<pair<long long, int> > >
      q;
  for (int i = 1; i <= n; i++) d[id][i] = -1;
  for (int i = 1; i <= n; i++) vis[i] = 0;
  d[id][x] = 0;
  q.push(make_pair(0, x));
  while (!q.empty()) {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = e.hd[u]; i; i = e.e[i].nxt) {
      int v = e.e[i].v;
      long long w = e.e[i].w;
      if (d[id][v] == -1 || d[id][u] + w < d[id][v]) {
        d[id][v] = d[id][u] + w;
        q.push(make_pair(d[id][v], v));
      }
    }
  }
}
int q;
int main() {
  scanf("%d%d", &n, &m);
  e.init();
  e2.init();
  for (int i = 0; i < m; i++) {
    int u, v, d;
    scanf("%d%d%d", &u, &v, &d);
    e.add(u, v, d);
    e.add(v, u, d);
  }
  dfs(1, 0);
  for (int i = 0; i <= 20; i++) father[1][i] = 1;
  dfs2(1, 1);
  for (int i = 1; i <= e.tot; i += 2) {
    if (!flag[i] && !flag[i + 1]) {
      v.push_back(e.e[i].u);
      v.push_back(e.e[i].v);
      ee.push_back(i);
    }
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 0; i < v.size(); i++) {
    id[v[i]] = i;
    dijkstra(v[i], i);
  }
  scanf("%d", &q);
  while (q--) {
    int u, v;
    scanf("%d%d", &u, &v);
    int r = getLCA(u, v);
    long long tmp_ans = cost[u] + cost[v] - 2ll * cost[r];
    for (int i = 0; i < ee.size(); i++) {
      int a = e.e[ee[i]].u;
      int b = e.e[ee[i]].v;
      long long w = e.e[ee[i]].w;
      long long tmp_ans_2 =
          min(d[id[a]][u] + d[id[b]][v] + w, d[id[b]][u] + d[id[a]][v] + w);
      tmp_ans = min(tmp_ans_2, tmp_ans);
    }
    printf("%I64d\n", tmp_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 N = 100010;
const int M = 300100;
int n, m;
struct Edge {
  struct edge {
    int u, v, nxt;
    long long w;
  } e[M];
  int tot, hd[N];
  void init() { tot = 0, memset(hd, 0, sizeof(hd)); }
  void add(int u, int v, long long w) {
    e[++tot].u = u, e[tot].v = v, e[tot].w = w, e[tot].nxt = hd[u], hd[u] = tot;
  }
} e, e2;
bool flag[M];
bool vis[N];
vector<int> v, ee;
int id[N];
long long d[42][N];
void dfs(int u, int f) {
  vis[u] = 1;
  for (int i = e.hd[u]; i; i = e.e[i].nxt) {
    int v = e.e[i].v;
    long long w = e.e[i].w;
    if (v == f || vis[v]) continue;
    flag[i] = 1;
    e2.add(u, v, w);
    e2.add(v, u, w);
    dfs(v, u);
  }
}
int deep[N], father[N][23];
long long cost[N];
void dfs2(int u, int f) {
  father[u][0] = f;
  for (int j = 1; j <= 20; j++) father[u][j] = father[father[u][j - 1]][j - 1];
  for (int i = e2.hd[u]; i; i = e2.e[i].nxt) {
    int v = e2.e[i].v;
    long long w = e2.e[i].w;
    if (v == f) continue;
    deep[v] = deep[u] + 1;
    cost[v] = cost[u] + w;
    dfs2(v, u);
  }
}
inline int getLCA(int x, int y) {
  if (deep[x] < deep[y]) swap(x, y);
  for (int i = 20; ~i; --i)
    if (deep[father[x][i]] >= deep[y]) x = father[x][i];
  if (x == y) return x;
  for (int i = 20; ~i; --i)
    if (father[x][i] != father[y][i]) x = father[x][i], y = father[y][i];
  return father[x][0];
}
void dijkstra(int x, int id) {
  priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                 greater<pair<long long, int> > >
      q;
  for (int i = 1; i <= n; i++) d[id][i] = -1;
  for (int i = 1; i <= n; i++) vis[i] = 0;
  d[id][x] = 0;
  q.push(make_pair(0, x));
  while (!q.empty()) {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = e.hd[u]; i; i = e.e[i].nxt) {
      int v = e.e[i].v;
      long long w = e.e[i].w;
      if (d[id][v] == -1 || d[id][u] + w < d[id][v]) {
        d[id][v] = d[id][u] + w;
        q.push(make_pair(d[id][v], v));
      }
    }
  }
}
int q;
int main() {
  scanf("%d%d", &n, &m);
  e.init();
  e2.init();
  for (int i = 0; i < m; i++) {
    int u, v, d;
    scanf("%d%d%d", &u, &v, &d);
    e.add(u, v, d);
    e.add(v, u, d);
  }
  dfs(1, 0);
  for (int i = 0; i <= 20; i++) father[1][i] = 1;
  dfs2(1, 1);
  for (int i = 1; i <= e.tot; i += 2) {
    if (!flag[i] && !flag[i + 1]) {
      v.push_back(e.e[i].u);
      v.push_back(e.e[i].v);
      ee.push_back(i);
    }
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 0; i < v.size(); i++) {
    id[v[i]] = i;
    dijkstra(v[i], i);
  }
  scanf("%d", &q);
  while (q--) {
    int u, v;
    scanf("%d%d", &u, &v);
    int r = getLCA(u, v);
    long long tmp_ans = cost[u] + cost[v] - 2ll * cost[r];
    for (int i = 0; i < ee.size(); i++) {
      int a = e.e[ee[i]].u;
      int b = e.e[ee[i]].v;
      long long w = e.e[ee[i]].w;
      long long tmp_ans_2 =
          min(d[id[a]][u] + d[id[b]][v] + w, d[id[b]][u] + d[id[a]][v] + w);
      tmp_ans = min(tmp_ans_2, tmp_ans);
    }
    printf("%I64d\n", tmp_ans);
  }
  return 0;
}

```