#include <bits/stdc++.h>
const int N = 1e5 + 5;
int Enum, H[N], nxt[N << 1], to[N << 1], len[N << 1], fa[N], dep[N], sz[N],
    son[N], top[N], sk[N];
long long dist[N], dis[23][N];
bool upd[N], nottree[N];
std::priority_queue<std::pair<long long, int> > q;
char IN[250000], *SS = IN, *TT = IN;
inline int read() {
  int now = 0;
  register char c =
      (SS == TT && (TT = (SS = IN) + fread(IN, 1, 250000, stdin), SS == TT)
           ? EOF
           : *SS++);
  for (; !isdigit(c);
       c = (SS == TT && (TT = (SS = IN) + fread(IN, 1, 250000, stdin), SS == TT)
                ? EOF
                : *SS++))
    ;
  for (; isdigit(c);
       now = now * 10 + c - '0',
       c = (SS == TT && (TT = (SS = IN) + fread(IN, 1, 250000, stdin), SS == TT)
                ? EOF
                : *SS++))
    ;
  return now;
}
inline int LCA(int u, int v) {
  while (top[u] != top[v])
    dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
  return dep[u] > dep[v] ? v : u;
}
int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void DFS1(int x) {
  int mx = 0;
  sz[x] = 1;
  for (int v, i = H[x]; i; i = nxt[i])
    if (!nottree[i] && (v = to[i]) != fa[x]) {
      fa[v] = x, dep[v] = dep[x] + 1, dist[v] = dist[x] + len[i], DFS1(v),
      sz[x] += sz[v];
      if (sz[v] > mx) mx = sz[v], son[x] = v;
    }
}
void DFS2(int x, int tp) {
  top[x] = tp;
  if (son[x]) {
    DFS2(son[x], tp);
    for (int i = H[x]; i; i = nxt[i])
      if (!nottree[i] && to[i] != fa[x] && to[i] != son[x]) DFS2(to[i], to[i]);
  }
}
void Dijkstra(long long *dis, int s, int n) {
  static bool vis[N];
  memset(vis, 0, sizeof vis);
  memset(dis, 0x3f, sizeof(long long) * (n + 1));
  dis[s] = 0, q.push(std::make_pair(0, s));
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (int i = H[x], v; i; i = nxt[i])
      if (dis[v = to[i]] > dis[x] + len[i])
        q.push(std::make_pair(-(dis[v] = dis[x] + len[i]), v));
  }
}
int main() {
  int n = read(), m = read();
  Enum = 1;
  for (int i = 1; i <= n; ++i) fa[i] = i;
  int tote = 0, cnt = 0;
  for (int i = 1, r1, r2, u, v, w; i <= m; ++i) {
    r1 = Find(u = read()), r2 = Find(v = read()), w = read();
    to[++Enum] = v, nxt[Enum] = H[u], H[u] = Enum, len[Enum] = w,
    to[++Enum] = u, nxt[Enum] = H[v], H[v] = Enum, len[Enum] = w;
    if (r1 == r2)
      nottree[Enum] = 1, nottree[Enum ^ 1] = 1, sk[++tote] = Enum;
    else
      fa[r1] = r2;
  }
  fa[1] = 1, DFS1(1), DFS2(1, 1);
  for (int i = 1; i <= tote; ++i) {
    int e = sk[i];
    if (!upd[to[e]]) upd[to[e]] = 1, Dijkstra(dis[++cnt], to[e], n);
  }
  for (int Q = read(), u, v; Q--;) {
    u = read(), v = read();
    long long ans = dist[u] + dist[v] - (dist[LCA(u, v)] << 1ll);
    for (int i = 1; i <= cnt; ++i) ans = std::min(ans, dis[i][u] + dis[i][v]);
    printf("%lld\n", ans);
  }
}

### Prompt

Please create a solution in Cpp 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>
const int N = 1e5 + 5;
int Enum, H[N], nxt[N << 1], to[N << 1], len[N << 1], fa[N], dep[N], sz[N],
    son[N], top[N], sk[N];
long long dist[N], dis[23][N];
bool upd[N], nottree[N];
std::priority_queue<std::pair<long long, int> > q;
char IN[250000], *SS = IN, *TT = IN;
inline int read() {
  int now = 0;
  register char c =
      (SS == TT && (TT = (SS = IN) + fread(IN, 1, 250000, stdin), SS == TT)
           ? EOF
           : *SS++);
  for (; !isdigit(c);
       c = (SS == TT && (TT = (SS = IN) + fread(IN, 1, 250000, stdin), SS == TT)
                ? EOF
                : *SS++))
    ;
  for (; isdigit(c);
       now = now * 10 + c - '0',
       c = (SS == TT && (TT = (SS = IN) + fread(IN, 1, 250000, stdin), SS == TT)
                ? EOF
                : *SS++))
    ;
  return now;
}
inline int LCA(int u, int v) {
  while (top[u] != top[v])
    dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
  return dep[u] > dep[v] ? v : u;
}
int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void DFS1(int x) {
  int mx = 0;
  sz[x] = 1;
  for (int v, i = H[x]; i; i = nxt[i])
    if (!nottree[i] && (v = to[i]) != fa[x]) {
      fa[v] = x, dep[v] = dep[x] + 1, dist[v] = dist[x] + len[i], DFS1(v),
      sz[x] += sz[v];
      if (sz[v] > mx) mx = sz[v], son[x] = v;
    }
}
void DFS2(int x, int tp) {
  top[x] = tp;
  if (son[x]) {
    DFS2(son[x], tp);
    for (int i = H[x]; i; i = nxt[i])
      if (!nottree[i] && to[i] != fa[x] && to[i] != son[x]) DFS2(to[i], to[i]);
  }
}
void Dijkstra(long long *dis, int s, int n) {
  static bool vis[N];
  memset(vis, 0, sizeof vis);
  memset(dis, 0x3f, sizeof(long long) * (n + 1));
  dis[s] = 0, q.push(std::make_pair(0, s));
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (int i = H[x], v; i; i = nxt[i])
      if (dis[v = to[i]] > dis[x] + len[i])
        q.push(std::make_pair(-(dis[v] = dis[x] + len[i]), v));
  }
}
int main() {
  int n = read(), m = read();
  Enum = 1;
  for (int i = 1; i <= n; ++i) fa[i] = i;
  int tote = 0, cnt = 0;
  for (int i = 1, r1, r2, u, v, w; i <= m; ++i) {
    r1 = Find(u = read()), r2 = Find(v = read()), w = read();
    to[++Enum] = v, nxt[Enum] = H[u], H[u] = Enum, len[Enum] = w,
    to[++Enum] = u, nxt[Enum] = H[v], H[v] = Enum, len[Enum] = w;
    if (r1 == r2)
      nottree[Enum] = 1, nottree[Enum ^ 1] = 1, sk[++tote] = Enum;
    else
      fa[r1] = r2;
  }
  fa[1] = 1, DFS1(1), DFS2(1, 1);
  for (int i = 1; i <= tote; ++i) {
    int e = sk[i];
    if (!upd[to[e]]) upd[to[e]] = 1, Dijkstra(dis[++cnt], to[e], n);
  }
  for (int Q = read(), u, v; Q--;) {
    u = read(), v = read();
    long long ans = dist[u] + dist[v] - (dist[LCA(u, v)] << 1ll);
    for (int i = 1; i <= cnt; ++i) ans = std::min(ans, dis[i][u] + dis[i][v]);
    printf("%lld\n", ans);
  }
}

```