#include <bits/stdc++.h>
void read(int& x) {
  x = 0;
  int flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= flag;
}
void read(long long& x) {
  x = 0;
  int flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= flag;
}
using namespace std;
const int maxn = 100030;
int n, m, q, head[maxn], tot, cnt, tot2, head2[maxn], f[maxn], vertex[50],
    par[maxn][20], dep[maxn];
long long dis[50][maxn], sum[maxn];
struct Edge {
  int to, nxt, dis;
} edge[maxn << 1], edge2[maxn << 1];
bool vis[maxn];
struct node {
  int num;
  long long dis;
  node(){};
  node(int a, long long b) { num = a, dis = b; }
  bool operator<(const node& a) const { return dis > a.dis; }
};
pair<pair<int, int>, int> line[maxn];
void add(int u, int v, int w) {
  edge[++tot].to = v, edge[tot].dis = w, edge[tot].nxt = head[u], head[u] = tot;
}
void add2(int u, int v, int w) {
  edge2[++tot2].to = v, edge2[tot2].dis = w, edge2[tot2].nxt = head2[u],
  head2[u] = tot2;
}
int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
void dfs(int u, int fa) {
  par[u][0] = fa, dep[u] = dep[fa] + 1;
  for (int i = head[u]; i; i = edge[i].nxt)
    if (edge[i].to != fa) {
      int v = edge[i].to;
      sum[v] = sum[u] + edge[i].dis;
      dfs(v, u);
    }
}
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 0; i <= (int)17; i++)
    if ((1 << i) & (dep[u] - dep[v])) u = par[u][i];
  if (u == v) return u;
  for (int i = 17; i >= 0; i--)
    if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
  return par[u][0];
}
void dij(int id, int s) {
  dis[id][s] = 0;
  priority_queue<node> pq;
  pq.push(node(s, 0));
  memset(vis, 0, sizeof(vis));
  while (!pq.empty()) {
    node u = pq.top();
    pq.pop();
    if (vis[u.num]) continue;
    vis[u.num] = 1;
    for (int i = head2[u.num]; i; i = edge2[i].nxt) {
      int v = edge2[i].to;
      if (dis[id][v] > dis[id][u.num] + edge2[i].dis) {
        dis[id][v] = dis[id][u.num] + edge2[i].dis;
        pq.push(node(v, dis[id][v]));
      }
    }
  }
}
int main() {
  read(n), read(m);
  for (int i = 1; i <= (int)m; i++) {
    int u, v, w;
    read(u), read(v), read(w);
    line[++cnt] = make_pair(make_pair(u, v), w);
    add2(u, v, w), add2(v, u, w);
  }
  for (int i = 1; i <= (int)n; i++) f[i] = i;
  cnt = 0;
  for (int i = 1; i <= (int)m; i++) {
    int u = line[i].first.first, v = line[i].first.second;
    int a = find(u), b = find(v);
    if (a != b) {
      f[a] = b;
      add(u, v, line[i].second);
      add(v, u, line[i].second);
    } else {
      vertex[++cnt] = u;
      vertex[++cnt] = v;
    }
  }
  dfs(1, 0);
  for (int j = 1; j <= (int)17; j++)
    for (int i = 1; i <= (int)n; i++) par[i][j] = par[par[i][j - 1]][j - 1];
  sort(vertex + 1, vertex + 1 + cnt);
  m = unique(vertex + 1, vertex + 1 + cnt) - vertex - 1;
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 1; i <= (int)m; i++) dij(i, vertex[i]);
  read(q);
  while (q--) {
    int u, v;
    read(u), read(v);
    long long ans = sum[u] + sum[v] - sum[lca(u, v)] * 2;
    for (int i = 1; i <= (int)m; i++) ans = min(ans, dis[i][u] + dis[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>
void read(int& x) {
  x = 0;
  int flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= flag;
}
void read(long long& x) {
  x = 0;
  int flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= flag;
}
using namespace std;
const int maxn = 100030;
int n, m, q, head[maxn], tot, cnt, tot2, head2[maxn], f[maxn], vertex[50],
    par[maxn][20], dep[maxn];
long long dis[50][maxn], sum[maxn];
struct Edge {
  int to, nxt, dis;
} edge[maxn << 1], edge2[maxn << 1];
bool vis[maxn];
struct node {
  int num;
  long long dis;
  node(){};
  node(int a, long long b) { num = a, dis = b; }
  bool operator<(const node& a) const { return dis > a.dis; }
};
pair<pair<int, int>, int> line[maxn];
void add(int u, int v, int w) {
  edge[++tot].to = v, edge[tot].dis = w, edge[tot].nxt = head[u], head[u] = tot;
}
void add2(int u, int v, int w) {
  edge2[++tot2].to = v, edge2[tot2].dis = w, edge2[tot2].nxt = head2[u],
  head2[u] = tot2;
}
int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
void dfs(int u, int fa) {
  par[u][0] = fa, dep[u] = dep[fa] + 1;
  for (int i = head[u]; i; i = edge[i].nxt)
    if (edge[i].to != fa) {
      int v = edge[i].to;
      sum[v] = sum[u] + edge[i].dis;
      dfs(v, u);
    }
}
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 0; i <= (int)17; i++)
    if ((1 << i) & (dep[u] - dep[v])) u = par[u][i];
  if (u == v) return u;
  for (int i = 17; i >= 0; i--)
    if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
  return par[u][0];
}
void dij(int id, int s) {
  dis[id][s] = 0;
  priority_queue<node> pq;
  pq.push(node(s, 0));
  memset(vis, 0, sizeof(vis));
  while (!pq.empty()) {
    node u = pq.top();
    pq.pop();
    if (vis[u.num]) continue;
    vis[u.num] = 1;
    for (int i = head2[u.num]; i; i = edge2[i].nxt) {
      int v = edge2[i].to;
      if (dis[id][v] > dis[id][u.num] + edge2[i].dis) {
        dis[id][v] = dis[id][u.num] + edge2[i].dis;
        pq.push(node(v, dis[id][v]));
      }
    }
  }
}
int main() {
  read(n), read(m);
  for (int i = 1; i <= (int)m; i++) {
    int u, v, w;
    read(u), read(v), read(w);
    line[++cnt] = make_pair(make_pair(u, v), w);
    add2(u, v, w), add2(v, u, w);
  }
  for (int i = 1; i <= (int)n; i++) f[i] = i;
  cnt = 0;
  for (int i = 1; i <= (int)m; i++) {
    int u = line[i].first.first, v = line[i].first.second;
    int a = find(u), b = find(v);
    if (a != b) {
      f[a] = b;
      add(u, v, line[i].second);
      add(v, u, line[i].second);
    } else {
      vertex[++cnt] = u;
      vertex[++cnt] = v;
    }
  }
  dfs(1, 0);
  for (int j = 1; j <= (int)17; j++)
    for (int i = 1; i <= (int)n; i++) par[i][j] = par[par[i][j - 1]][j - 1];
  sort(vertex + 1, vertex + 1 + cnt);
  m = unique(vertex + 1, vertex + 1 + cnt) - vertex - 1;
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 1; i <= (int)m; i++) dij(i, vertex[i]);
  read(q);
  while (q--) {
    int u, v;
    read(u), read(v);
    long long ans = sum[u] + sum[v] - sum[lca(u, v)] * 2;
    for (int i = 1; i <= (int)m; i++) ans = min(ans, dis[i][u] + dis[i][v]);
    printf("%lld\n", ans);
  }
  return 0;
}

```