#include <bits/stdc++.h>
using namespace std;
long long n, m, first[200100], deep[200100], dep[200100], fa[200100][20],
    d[50][200100], num[200100], bb = 1, cnt, Q, ans;
bool vis[200100], in[200100];
struct Bn {
  long long to, next, quan;
} bn[200100 << 1];
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >,
               greater<pair<long long, long long> > >
    pq;
inline void add(long long u, long long v, long long w) {
  bb++;
  bn[bb].to = v;
  bn[bb].next = first[u];
  bn[bb].quan = w;
  first[u] = bb;
}
void dfs(long long now) {
  long long p, q;
  for (p = first[now]; p != -1; p = bn[p].next) {
    if (deep[bn[p].to]) continue;
    vis[p >> 1] = 1;
    fa[bn[p].to][0] = now;
    deep[bn[p].to] = deep[now] + bn[p].quan;
    dep[bn[p].to] = dep[now] + 1;
    dfs(bn[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 = 16; dep[u] != dep[v]; i--) {
    if (dep[fa[u][i]] >= dep[v]) {
      u = fa[u][i];
    }
  }
  for (i = 16; 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 get(long long u, long long v) {
  long long i, j, p, q, a, b;
  pair<long long, long long> tmp;
  pq.push(make_pair(0, u));
  d[v][u] = 0;
  for (; !pq.empty();) {
    tmp = pq.top();
    pq.pop();
    a = tmp.first, b = tmp.second;
    if (a > d[v][b]) continue;
    for (p = first[b]; p != -1; p = bn[p].next) {
      if (d[v][bn[p].to] <= a + bn[p].quan) continue;
      d[v][bn[p].to] = a + bn[p].quan;
      pq.push(make_pair(d[v][bn[p].to], bn[p].to));
    }
  }
}
int main() {
  memset(d, 0x3f, sizeof(d));
  memset(first, -1, sizeof(first));
  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 <= 16; i++) {
    for (j = 1; j <= n; j++) {
      fa[j][i] = fa[fa[j][i - 1]][i - 1];
    }
  }
  for (i = 2; i <= bb; i += 2) {
    if (vis[(i >> 1)]) continue;
    p = bn[i].to;
    if (!in[p]) {
      num[++cnt] = p;
      in[p] = 1;
      get(p, cnt);
    }
    p = bn[i + 1].to;
    if (!in[p]) {
      num[++cnt] = p;
      in[p] = 1;
      get(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);
  }
}
