#include <bits/stdc++.h>
using namespace std;
const int maxn = 16;
long long n, m, head[200100], deep[200100], dep[200100], fa[200100][20],
    d[50][200100], num[200100], tot = 1, cnt, Q, ans;
bool vis[200100], in[200100];
struct edge {
  long long to, next, w;
} edges[200100 << 1];
struct node {
  long long dist, u;
  node(long long dist = 0, long long u = 0) : dist(dist), u(u) {}
  bool operator<(node rhs) const { return u > rhs.u; }
};
priority_queue<node> pq;
inline void add(long long u, long long v, long long w) {
  tot++;
  edges[tot].to = v;
  edges[tot].next = head[u];
  edges[tot].w = w;
  head[u] = tot;
}
void dfs(long long now) {
  long long p, q;
  for (p = head[now]; p; p = edges[p].next) {
    if (deep[edges[p].to]) continue;
    vis[p >> 1] = 1;
    fa[edges[p].to][0] = now;
    deep[edges[p].to] = deep[now] + edges[p].w;
    dep[edges[p].to] = dep[now] + 1;
    dfs(edges[p].to);
  }
}
inline long long lca(long long u, long long v) {
  if (dep[u] < dep[v]) swap(u, v);
  long long i, j;
  for (i = maxn; dep[u] != dep[v]; i--) {
    if (dep[fa[u][i]] >= dep[v]) {
      u = fa[u][i];
    }
  }
  for (i = maxn; i >= 0; i--) {
    if (fa[u][i] != fa[v][i]) {
      u = fa[u][i];
      v = fa[v][i];
    }
  }
  if (u != v) u = fa[u][0];
  return u;
}
inline long long dis(long long u, long long v) {
  long long l = lca(u, v);
  return deep[u] - deep[l] * 2 + deep[v];
}
inline void dijkstra(long long u, long long cnt) {
  long long i, j, p, q, a, b;
  node tmp;
  pq.push(node(0, u));
  d[cnt][u] = 0;
  while (!pq.empty()) {
    tmp = pq.top();
    pq.pop();
    a = tmp.dist, b = tmp.u;
    if (a > d[cnt][b]) continue;
    for (p = head[b]; p; p = edges[p].next) {
      int v = edges[p].to, w = edges[p].w;
      if (d[cnt][v] <= a + w) continue;
      d[cnt][v] = a + w;
      pq.push(node(d[cnt][v], v));
    }
  }
}
int main() {
  memset(d, 0x3f, sizeof(d));
  long long i, j, p, q, o;
  cin >> n >> m;
  for (i = 1; i <= m; i++) {
    scanf("%lld%lld%lld", &p, &q, &o);
    add(p, q, o);
    add(q, p, o);
  }
  deep[1] = dep[1] = 1;
  dfs(1);
  for (i = 1; i <= maxn; i++) {
    for (j = 1; j <= n; j++) {
      fa[j][i] = fa[fa[j][i - 1]][i - 1];
    }
  }
  for (i = 2; i <= tot; i += 2) {
    if (vis[(i >> 1)]) continue;
    p = edges[i].to;
    if (!in[p]) {
      num[++cnt] = p;
      in[p] = 1;
      dijkstra(p, cnt);
    }
    p = edges[i + 1].to;
    if (!in[p]) {
      num[++cnt] = p;
      in[p] = 1;
      dijkstra(p, cnt);
    }
  }
  cin >> Q;
  for (i = 1; i <= Q; i++) {
    scanf("%lld%lld", &p, &q);
    ans = dis(p, q);
    for (j = 1; j <= cnt; j++) {
      ans = min(ans, dis(p, num[j]) + d[j][q]);
    }
    printf("%lld\n", ans);
  }
}
