#include <bits/stdc++.h>
#define upd(x, y) x = min(x, y)
using namespace std;
int scan() {
  int x = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar());
  for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
  return x;
}
int top, stk[11];
void print(int x) {
  if (x < 0) putchar('-'), x = -x;
  do stk[++top] = x % 10, x /= 10; while (x);
  while (top) putchar('0' + stk[top--]);
}
const int N = 1e6 + 5;
int n, m, q, deg[N], s[N], t[N], ans[N], rec[N];
queue<int> Q;
unordered_map<int, int> E[N];
vector<int> tmp, ask3[N], ask4[N];
vector<pair<int, int>> ver[N], Rv[N], Lu[N];
vector<pair<int, pair<int, int>>> ask1[N], ask2[N];
int main() {
  n = scan(), m = scan();
  while (m--) {
    int u = scan(), v = scan(), w = scan();
    ++deg[u], ++deg[v];
    if (E[u].find(v) == E[u].end() || w < E[u][v]) E[u][v] = E[v][u] = w;
    ver[u].emplace_back(v, w), ver[v].emplace_back(u, w);
  }
  for (int u = 1; u <= n; ++u) if (deg[u] <= 5) Q.emplace(u), deg[u] = -1;
  while (!Q.empty()) {
    int u = Q.front(); Q.pop(), deg[u] = -2;
    for (auto it: ver[u]) {
      int v = it.first, w = it.second;
      if (deg[v] > -1 && --deg[v] <= 5) Q.emplace(v), deg[v] = -1;
      if (deg[v] > -2) Rv[u].emplace_back(v, w), Lu[u].emplace_back(v, w);
    }
  }
  q = scan(), memset(ans, 0x3f, sizeof ans);
  for (int i = 1; i <= q; ++i) {
    s[i] = scan(), t[i] = scan();
    if (E[s[i]].find(t[i]) != E[s[i]].end()) ans[i] = E[s[i]][t[i]];
    for (auto it: Rv[s[i]]) {
      int v = it.first, w = it.second;
      ask1[v].emplace_back(i, make_pair(t[i], w)),
      ask2[t[i]].emplace_back(i, make_pair(v, w));
      if (E[v].find(t[i]) != E[v].end()) upd(ans[i], w + E[v][t[i]]);
    }
    for (auto it: Lu[t[i]]) {
      int u = it.first, w = it.second;
      ask1[s[i]].emplace_back(i, make_pair(u, w)),
      ask2[u].emplace_back(i, make_pair(s[i], w));
      if (E[u].find(s[i]) != E[u].end()) upd(ans[i], E[s[i]][u] + w);
    }
    ask3[s[i]].emplace_back(i), ask4[t[i]].emplace_back(i);
  }
  memset(rec, 0x3f, sizeof rec);
  for (int u = 1; u <= n; ++u) {
    if (!ask1[u].empty()) {
      for (auto it: ver[u]) {
        int v = it.first, w = it.second;
        for (auto it2: Rv[v]) {
          int v2 = it2.first, w2 = it2.second;
          upd(rec[v2], w + w2), tmp.emplace_back(v2);
        }
      }
      for (auto it: ask1[u])
        upd(ans[it.first], rec[it.second.first] + it.second.second);
      for (int v: tmp) rec[v] = rec[0];
      tmp.clear();
    }
    if (!ask2[u].empty()) {
      for (auto it: ver[u]) {
        int v = it.first, w = it.second;
        for (auto it2: Lu[v]) {
          int v2 = it2.first, w2 = it2.second;
          upd(rec[v2], w + w2), tmp.emplace_back(v2);
        }
      }
      for (auto it: ask2[u])
        upd(ans[it.first], rec[it.second.first] + it.second.second);
      for (int v: tmp) rec[v] = rec[0];
      tmp.clear();
    }
    if (!ask3[u].empty()) {
      for (auto it: ver[u]) {
        int v = it.first, w = it.second;
        for (auto it2: Rv[v]) {
          int v2 = it2.first, w2 = it2.second;
          upd(rec[v2], w + w2);
          for (auto it3: Rv[v2]) {
            int v3 = it3.first, w3 = it3.second;
            upd(rec[v3], w + w2 + w3), tmp.emplace_back(v3);
          }
        }
      }
      for (auto i: ask3[u]) upd(ans[i], rec[t[i]]);
      for (int v: tmp) rec[v] = rec[0];
      tmp.clear();
    }
    if (!ask4[u].empty()) {
      for (auto it: ver[u]) {
        int v = it.first, w = it.second;
        for (auto it2: Lu[v]) {
          int v2 = it2.first, w2 = it2.second;
          for (auto it3: Lu[v2]) {
            int v3 = it3.first, w3 = it3.second;
            upd(rec[v3], w + w2 + w3), tmp.emplace_back(v3);
          }
        }
      }
      for (auto i: ask4[u]) upd(ans[i], rec[s[i]]);
      for (int v: tmp) rec[v] = rec[0];
      tmp.clear();
    }
  }
  for (int i = 1; i <= q; ++i)
    print(ans[i] == ans[0] ? -1 : ans[i]), putchar('\n');
  return 0;
}