#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


#include <ext/pb_ds/assoc_container.hpp>
using __gnu_pbds::gp_hash_table;

// https://codeforces.com/blog/entry/62393
#include <chrono>
struct Hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  size_t operator()(const pair<int, int> &a) const {
    return operator()((uint64_t)a.first << 32 | a.second);
  }
};
template <class K, class V> using Map = gp_hash_table<K, V, Hash>;


/*
    ==> *
  * <==  
    ==>   ==> *
    ==> * <==  
    <-- u -->  
  * <==   <==  
    ==>   ==>   ==> *
    ==>   ==> * <==  
    ==>   <-- u -->  
    ==> * <==   <==  
    <-- u -->   -->  
    <-- u -->   <==  
    <--   <-- u -->  
  * <==   <==   <==  
*/

constexpr int INF = 1001001001;

int N, M;
vector<int> A, B, C;
int Q;
vector<int> S, T;

int main() {
  for (; ~scanf("%d%d", &N, &M); ) {
    A.resize(M);
    B.resize(M);
    C.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%d", &A[i], &B[i], &C[i]);
      --A[i];
      --B[i];
    }
    scanf("%d", &Q);
    S.resize(Q);
    T.resize(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d%d", &S[q], &T[q]);
      --S[q];
      --T[q];
    }
    
    // orientation s.t. outdeg <= 5
    {
      vector<vector<int>> graph(N);
      for (int i = 0; i < M; ++i) {
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
      }
      using Entry = pair<int, int>;
      priority_queue<Entry, vector<Entry>, greater<Entry>> que;
      vector<int> deg(N, 0);
      for (int u = 0; u < N; ++u) que.emplace(deg[u] = graph[u].size(), u);
      int id = 0;
      vector<int> ids(N, -1);
      for (; que.size(); ) {
        const int u = que.top().second;
        que.pop();
        if (!~ids[u]) {
          ids[u] = id++;
          for (const int v : graph[u]) que.emplace(--deg[v], v);
        }
      }
// cerr<<"ids = "<<ids<<endl;
      for (int i = 0; i < M; ++i) {
        A[i] = ids[A[i]];
        B[i] = ids[B[i]];
        if (A[i] > B[i]) swap(A[i], B[i]);
      }
      for (int q = 0; q < Q; ++q) {
        S[q] = ids[S[q]];
        T[q] = ids[T[q]];
        if (S[q] > T[q]) swap(S[q], T[q]);
      }
    }
    
    vector<vector<pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) graph[A[i]].emplace_back(C[i], B[i]);
    
    Map<pair<int, int>, int> ma[4];
    auto update = [&](int k, int u, int v, int c) -> void {
      if (u > v) swap(u, v);
      auto it = ma[k].find(make_pair(u, v));
      if (it != ma[k].end()) {
        chmin(it->second, c);
      } else {
        ma[k][make_pair(u, v)] = c;
      }
    };
    for (int u = 0; u < N; ++u) {
      for (const auto &euv : graph[u]) for (const auto &euw : graph[u]) {
        const int v = euv.second;
        const int w = euw.second;
        if (v < w) {
          const int c = euv.first + euw.first;
          update(2, v, w, c);
          for (const auto &evx : graph[v]) update(3, evx.second, w, c + evx.first);
          for (const auto &ewx : graph[w]) update(3, v, ewx.second, c + ewx.first);
        }
      }
    }
    
    for (int q = 0; q < Q; ++q) {
      int ans = INF;
      auto check = [&](int l, int u, int v, int c) -> void {
        if (u == v) {
          chmin(ans, c);
        } else {
          for (int k = 2; l + k <= 3; ++k) {
            auto it = ma[k].find(make_pair(u, v));
            if (it != ma[k].end()) {
              chmin(ans, c + it->second);
            }
          }
        }
      };
      const int s0 = S[q], t0 = T[q];
      check(0, s0, t0, 0);
      for (const auto &f01 : graph[t0]) {
        const int t1 = f01.second;
        check(1, s0, t1, f01.first);
        for (const auto &f12 : graph[t1]) {
          const int t2 = f12.second;
          check(2, s0, t2, f01.first + f12.first);
          for (const auto &f23 : graph[t2]) {
            const int t3 = f23.second;
            check(3, s0, t3, f01.first + f12.first + f23.first);
          }
        }
      }
      for (const auto &e01 : graph[s0]) {
        const int s1 = e01.second;
        check(1, s1, t0, e01.first);
        for (const auto &f01 : graph[t0]) {
          const int t1 = f01.second;
          check(2, s1, t1, e01.first + f01.first);
          for (const auto &f12 : graph[t1]) {
            const int t2 = f12.second;
            check(3, s1, t2, e01.first + f01.first + f12.first);
          }
        }
        for (const auto &e12 : graph[s1]) {
          const int s2 = e12.second;
          check(2, s2, t0, e01.first + e12.first);
          for (const auto &f01 : graph[t0]) {
            const int t1 = f01.second;
            check(3, s2, t1, e01.first + e12.first + f01.first);
          }
          for (const auto &e23 : graph[s2]) {
            const int s3 = e23.second;
            check(3, s3, t0, e01.first + e12.first + e23.first);
          }
        }
      }
      printf("%d\n", (ans < INF) ? ans : -1);
    }
  }
  return 0;
}