#include <bits/stdc++.h>
using namespace std;
const int M = 100 * 1000 + 10;
int n, m, q;
int fa[M];
struct query {
  int u, v;
  long long ans;
} qy[M];
struct edge {
  int u, v, wt;
} extra[30];
int cnt_extra = 0;
int head[M] = {0};
vector<vector<int> > ask(M);
struct Edge {
  int to, nx, wt;
} e[M * 2];
int cnt = 1;
void add(int u, int v, int wt) {
  e[cnt].to = v, e[cnt].wt = wt;
  e[cnt].nx = head[u];
  head[u] = cnt++;
}
int fd(int x) { return x == fa[x] ? x : fa[x] = fd(fa[x]); }
bool join(int u, int v) {
  int fu = fd(u), fv = fd(v);
  if (fu == fv) return false;
  fa[fv] = fu;
  return true;
}
bool vis[M] = {0};
void init() {
  for (int i = 0; i < n + 1; ++i) fa[i] = i;
}
long long dis[M] = {0};
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               greater<pair<long long, int> > >
    qq;
void dij(int kk) {
  long long up = 1e17;
  for (int i = 0; i < n + 1; ++i) dis[i] = up;
  dis[kk] = 0;
  while (!qq.empty()) qq.pop();
  for (int i = 1; i < n + 1; ++i) qq.push(make_pair(dis[i], i));
  while (!qq.empty()) {
    pair<long long, int> tmp = qq.top();
    qq.pop();
    long long di = tmp.first;
    int id = tmp.second;
    if (dis[id] < di) continue;
    for (int i = head[id]; i; i = e[i].nx) {
      if (dis[e[i].to] > dis[id] + e[i].wt) {
        dis[e[i].to] = dis[id] + e[i].wt;
        qq.push(make_pair(dis[e[i].to], e[i].to));
      }
    }
  }
}
int gt(int x, const query& ot) { return x == ot.u ? ot.v : ot.u; }
void dfs(int cur) {
  vis[cur] = 1;
  int all = ask[cur].size();
  for (int i = head[cur]; i; i = e[i].nx) {
    if (vis[e[i].to]) continue;
    dfs(e[i].to);
    join(cur, e[i].to);
  }
  for (int i = 0; i < all; ++i) {
    int ot = gt(cur, qy[ask[cur][i]]);
    if (vis[ot]) {
      qy[ask[cur][i]].ans = dis[cur] + dis[ot] - (dis[fd(ot)] << 1);
    }
  }
}
void tarjan() {
  init();
  memset(vis, 0, sizeof(vis));
  dfs(1);
}
void upd() {
  for (int i = 0; i < q; ++i)
    qy[i].ans = min(qy[i].ans, dis[qy[i].u] + dis[qy[i].v]);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  int u, v, w;
  init();
  for (int i = 0; i < m; ++i) {
    cin >> u >> v >> w;
    if (join(u, v)) {
      add(u, v, w);
      add(v, u, w);
    } else {
      extra[cnt_extra].u = u;
      extra[cnt_extra].v = v;
      extra[cnt_extra].wt = w;
      ++cnt_extra;
    }
  }
  dij(1);
  cin >> q;
  for (int i = 0; i < q; ++i) {
    cin >> qy[i].u >> qy[i].v;
    ask[qy[i].u].push_back(i);
    ask[qy[i].v].push_back(i);
  }
  tarjan();
  for (int i = 0; i < cnt_extra; ++i) {
    add(extra[i].u, extra[i].v, extra[i].wt);
    add(extra[i].v, extra[i].u, extra[i].wt);
  }
  for (int i = 0; i < cnt_extra; ++i) {
    dij(extra[i].u);
    upd();
    dij(extra[i].v);
    upd();
  }
  for (int i = 0; i < q; ++i) cout << qy[i].ans << endl;
  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 M = 100 * 1000 + 10;
int n, m, q;
int fa[M];
struct query {
  int u, v;
  long long ans;
} qy[M];
struct edge {
  int u, v, wt;
} extra[30];
int cnt_extra = 0;
int head[M] = {0};
vector<vector<int> > ask(M);
struct Edge {
  int to, nx, wt;
} e[M * 2];
int cnt = 1;
void add(int u, int v, int wt) {
  e[cnt].to = v, e[cnt].wt = wt;
  e[cnt].nx = head[u];
  head[u] = cnt++;
}
int fd(int x) { return x == fa[x] ? x : fa[x] = fd(fa[x]); }
bool join(int u, int v) {
  int fu = fd(u), fv = fd(v);
  if (fu == fv) return false;
  fa[fv] = fu;
  return true;
}
bool vis[M] = {0};
void init() {
  for (int i = 0; i < n + 1; ++i) fa[i] = i;
}
long long dis[M] = {0};
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               greater<pair<long long, int> > >
    qq;
void dij(int kk) {
  long long up = 1e17;
  for (int i = 0; i < n + 1; ++i) dis[i] = up;
  dis[kk] = 0;
  while (!qq.empty()) qq.pop();
  for (int i = 1; i < n + 1; ++i) qq.push(make_pair(dis[i], i));
  while (!qq.empty()) {
    pair<long long, int> tmp = qq.top();
    qq.pop();
    long long di = tmp.first;
    int id = tmp.second;
    if (dis[id] < di) continue;
    for (int i = head[id]; i; i = e[i].nx) {
      if (dis[e[i].to] > dis[id] + e[i].wt) {
        dis[e[i].to] = dis[id] + e[i].wt;
        qq.push(make_pair(dis[e[i].to], e[i].to));
      }
    }
  }
}
int gt(int x, const query& ot) { return x == ot.u ? ot.v : ot.u; }
void dfs(int cur) {
  vis[cur] = 1;
  int all = ask[cur].size();
  for (int i = head[cur]; i; i = e[i].nx) {
    if (vis[e[i].to]) continue;
    dfs(e[i].to);
    join(cur, e[i].to);
  }
  for (int i = 0; i < all; ++i) {
    int ot = gt(cur, qy[ask[cur][i]]);
    if (vis[ot]) {
      qy[ask[cur][i]].ans = dis[cur] + dis[ot] - (dis[fd(ot)] << 1);
    }
  }
}
void tarjan() {
  init();
  memset(vis, 0, sizeof(vis));
  dfs(1);
}
void upd() {
  for (int i = 0; i < q; ++i)
    qy[i].ans = min(qy[i].ans, dis[qy[i].u] + dis[qy[i].v]);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  int u, v, w;
  init();
  for (int i = 0; i < m; ++i) {
    cin >> u >> v >> w;
    if (join(u, v)) {
      add(u, v, w);
      add(v, u, w);
    } else {
      extra[cnt_extra].u = u;
      extra[cnt_extra].v = v;
      extra[cnt_extra].wt = w;
      ++cnt_extra;
    }
  }
  dij(1);
  cin >> q;
  for (int i = 0; i < q; ++i) {
    cin >> qy[i].u >> qy[i].v;
    ask[qy[i].u].push_back(i);
    ask[qy[i].v].push_back(i);
  }
  tarjan();
  for (int i = 0; i < cnt_extra; ++i) {
    add(extra[i].u, extra[i].v, extra[i].wt);
    add(extra[i].v, extra[i].u, extra[i].wt);
  }
  for (int i = 0; i < cnt_extra; ++i) {
    dij(extra[i].u);
    upd();
    dij(extra[i].v);
    upd();
  }
  for (int i = 0; i < q; ++i) cout << qy[i].ans << endl;
  return 0;
}

```