#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10, LOGN = 20;
const long long INF = 1e18;
vector<pair<int, int> > G[MAXN];
struct UnionFind {
  vector<int> f;
  void init(int n) {
    f.clear();
    f.insert(f.begin(), n, -1);
  }
  int comp(int x) { return f[x] == -1 ? x : f[x] = comp(f[x]); }
  bool join(int i, int j) {
    bool con = comp(i) == comp(j);
    if (!con) f[comp(i)] = comp(j);
    return con;
  }
} uf;
int N, f[MAXN][LOGN], L[MAXN];
long long C[MAXN];
void dfs(int v, int fa = -1, long long c = 0, int lvl = 0) {
  f[v][0] = fa, L[v] = lvl, C[v] = c;
  for (auto e : G[v]) {
    int u = e.first, cc = e.second;
    if (u != fa) dfs(u, v, c + cc, lvl + 1);
  }
}
void build() {
  for (int k = int(0); k < int(LOGN - 1); k++)
    for (int i = int(0); i < int(N); i++)
      if (f[i][k] != -1) f[i][k + 1] = f[f[i][k]][k];
}
int climb(int a, int d) {
  if (!d) return a;
  for (int i = int((31 - __builtin_clz(L[a])) + 1 - 1); i >= int(0); i--)
    if (1 << i <= d) a = f[a][i], d -= 1 << i;
  return a;
}
int lca(int a, int b) {
  if (L[a] < L[b]) swap(a, b);
  a = climb(a, L[a] - L[b]);
  if (a == b) return a;
  for (int i = int((31 - __builtin_clz(L[a])) + 1 - 1); i >= int(0); i--)
    if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
  return f[a][0];
}
long long dist(int a, int b) { return C[a] + C[b] - 2 * C[lca(a, b)]; }
const int MAXE = 50;
int ha[MAXN], cnt = 1;
long long distG[MAXE][MAXE], distAG[MAXN][MAXE];
int deha[MAXE];
inline void go(int u) {
  if (ha[u] == 0) {
    ha[u] = cnt;
    deha[cnt] = u;
    cnt++;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  fill(distG[0], distG[MAXE], INF);
  int m;
  cin >> N >> m;
  uf.init(N);
  for (int _ = int(0); _ < int(m); _++) {
    int u, v;
    long long d;
    cin >> u >> v >> d;
    u--;
    v--;
    if (uf.comp(u) != uf.comp(v)) {
      uf.join(u, v);
      G[u].emplace_back(v, d);
      G[v].emplace_back(u, d);
    } else {
      go(u);
      go(v);
      int nu = ha[u], nv = ha[v];
      distG[nu][nv] = distG[nv][nu] = min(distG[nu][nv], d);
    }
  }
  dfs(0);
  build();
  for (int i = int(1); i < int(cnt); i++)
    for (int j = int(1); j < int(cnt); j++)
      distG[i][j] = min(distG[i][j], dist(deha[i], deha[j]));
  for (int k = int(1); k < int(cnt); k++)
    for (int i = int(1); i < int(cnt); i++)
      for (int j = int(1); j < int(cnt); j++)
        distG[i][j] = min(distG[i][j], distG[i][k] + distG[k][j]);
  for (int i = int(0); i < int(N); i++)
    for (int j = int(1); j < int(cnt); j++) distAG[i][j] = dist(i, deha[j]);
  int q;
  cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    long long ans = dist(u, v);
    for (int i = int(1); i < int(cnt); i++)
      for (int j = int(1); j < int(cnt); j++) {
        ans = min(ans, distAG[u][i] + distAG[v][j] + distG[i][j]);
      }
    cout << ans << '\n';
  }
  return 0;
}
