#include <bits/stdc++.h>
using namespace std;
inline int getint() {
  register int r = 0, f = 1;
  register char c = getchar();
  while (!isdigit(c)) f = c == '-' ? -f : f, c = getchar();
  while (isdigit(c)) r = (r << 3) + (r << 1) + (c ^ 48), c = getchar();
  return r * f;
}
const int N = 1e5 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
int n, m;
struct Edge {
  int to, nxt;
  long long w;
} edge[N << 2];
int head[N << 1], cnt;
inline void add(int u, int v, long long w) {
  edge[++cnt] = (Edge){v, head[u], w}, head[u] = cnt;
}
int fa[N], dep[N], siz[N], top[N];
long long sum[N];
void dfs1(int u) {
  siz[u] = 1;
  for (int v = head[u]; v; v = edge[v].nxt)
    if (edge[v].to != fa[u])
      fa[edge[v].to] = u, dep[edge[v].to] = dep[u] + 1,
      sum[edge[v].to] = sum[u] + edge[v].w, dfs1(edge[v].to),
      siz[u] += siz[edge[v].to];
}
void dfs2(int u, int g) {
  top[u] = g;
  int son = 0;
  for (int v = head[u]; v; v = edge[v].nxt)
    if (edge[v].to != fa[u] && siz[edge[v].to] > siz[son]) son = edge[v].to;
  if (!son) return;
  dfs2(son, g);
  for (int v = head[u]; v; v = edge[v].nxt)
    if (edge[v].to != fa[u] && edge[v].to != son) dfs2(edge[v].to, edge[v].to);
}
int lca(int a, int b) {
  while (top[a] != top[b]) {
    if (dep[top[a]] < dep[top[b]]) swap(a, b);
    a = fa[top[a]];
  }
  if (dep[a] > dep[b]) swap(a, b);
  return a;
}
long long dis[50][N];
struct pii {
  long long fst;
  int snd;
  bool operator>(const pii &b) const { return fst > b.fst; }
};
priority_queue<pii, vector<pii>, greater<pii> > q;
pii mp(long long a, int b) { return (pii){a, b}; }
int poi[50], cc;
void dijkstra(int s) {
  dis[s][poi[s]] = 0, q.push(mp(0, poi[s] + n));
  pii x;
  int u;
  while (!q.empty()) {
    x = q.top(), u = x.snd, q.pop();
    if (x.fst != dis[s][u - n]) continue;
    for (int v = head[u]; v; v = edge[v].nxt)
      if (dis[s][edge[v].to - n] > dis[s][u - n] + edge[v].w)
        dis[s][edge[v].to - n] = dis[s][u - n] + edge[v].w,
                            q.push(mp(dis[s][edge[v].to - n], edge[v].to));
  }
}
int p[N];
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
int main() {
  n = getint(), m = getint();
  int u, v, w;
  for (int i = 1; i <= n; i++) p[i] = i;
  for (int i = 1; i <= m; i++) {
    u = getint(), v = getint(), w = getint(), add(u + n, v + n, w),
    add(v + n, u + n, w);
    if (find(u) != find(v))
      p[find(u)] = find(v), add(u, v, w), add(v, u, w);
    else
      poi[++cc] = u, poi[++cc] = v;
  }
  dep[1] = 1, dfs1(1), dfs2(1, 1);
  memset(dis, 0x3f, sizeof dis);
  for (int i = 1; i <= cc; i++) dijkstra(i);
  int q = getint(), x, y;
  long long ans;
  while (q--) {
    x = getint(), y = getint(), ans = sum[x] + sum[y] - 2 * sum[lca(x, y)];
    for (int i = 1; i <= cc; i++) ans = min(ans, dis[i][x] + dis[i][y]);
    printf("%lld\n", ans);
  }
  return 0;
}
