#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))

typedef long long ll;
typedef double db;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }

constexpr int inf = 1e9;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> G(n), L(n), R(n);
    vi du(n), rk(n); int rk_ = 1;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        du[u]++, du[v]++;
        G[u].pb(Mp(v, w));
        G[v].pb(Mp(u, w));
    }
    queue<int> qu;
    for(int i = 0; i < n; i++) if(du[i] <= 5) qu.push(i), rk[i] = rk_++;
    for(int i = 0; i < n; i++) {
        int x = qu.front(); qu.pop();
        for(auto [y, w] : G[x]) if(!rk[y]) {
            if(--du[y] <= 5) {
                qu.push(y);
                rk[y] = rk_++;
            }
        }
    }
    for(int x = 0; x < n; x++) {
        for(auto [y, w] : G[x]) {
            if(rk[x] < rk[y]) R[x].pb(Mp(y, w));
            else L[x].pb(Mp(y, w));
        }
    }

    int q;
    cin >> q;
    vi ans(q, inf);
    vector<vector<pii>> st(n), ed(n);
    for(int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        if(rk[u] > rk[v]) swap(u, v);
        st[u].pb(Mp(v, i));
        ed[v].pb(Mp(u, i));
    }
    vi dis(n, inf);
    for(int p1 = 0; p1 < n; p1++) {
        vi ch;
        for(auto [p2, w1] : L[p1]) {
            for(auto [p3, w2] : R[p2]) if(p3 != p1) {
                ch.pb(p3), dis[p3] = min(dis[p3], w1 + w2); // LR
                for(auto [p4, w3] : R[p3]) {
                    ch.pb(p4), dis[p4] = min(dis[p4], w1 + w2 + w3); // LRR
                }
            }
        }
        for(auto [T, i] : st[p1]) {
            ans[i] = min(ans[i], dis[T]);
        }
        for(auto [S, i] : ed[p1]) {
            ans[i] = min(ans[i], dis[S]);
        }
        for(auto i : ch) dis[i] = inf;
    }
    vector<array<int, 3>> ans2;
    vector<vector<pii>> st2(n), ed2(n);
    for(int p1 = 0; p1 < n; p1++) {
        for(auto [p2, w1] : R[p1]) { // R__/__L
            auto ins = [&](int s, int t, int qid) {
                if(s == t) {
                    ans[qid] = min(ans[qid], w1);
                    return;
                }
                if(rk[s] > rk[t]) swap(s, t);
                st2[s].pb(Mp(t, SZ(ans2)));
                ed2[t].pb(Mp(s, SZ(ans2)));
                ans2.pb({qid, inf, w1});
            };
            for(auto [T, i] : st[p1]) {
                ins(p2, T, i);
            }
            for(auto [S, i] : ed[p1]) {
                ins(S, p2, i);
            }
        }
    }
    for(int p1 = 0; p1 < n; p1++) {
        vi ch;
        for(auto [p2, w1] : L[p1]) { // LR
            for(auto [p3, w2] : R[p2]) {
                ch.pb(p3), dis[p3] = min(dis[p3], w1 + w2);
            }
        }
        for(auto [T, i] : st2[p1]) {
            ans2[i][1] = min(ans2[i][1], dis[T]);
        }
        for(auto i : ch) dis[i] = inf;
    }
    int cnt = 0;
    for(int p1 = 0; p1 < n; p1++) {
        for(auto [p2, w1] : R[p1]) {
            auto ins = [&](int s, int t, int qid) {
                if(s == t) {
                    ans2[qid][1] = min(ans2[qid][1], w1);
                    return;
                }
                if(rk[s] > rk[t]) swap(s, t);
                for(auto [T, w] : R[s]) if(T == t) {
                    ans2[qid][1] = min(ans2[qid][1], w1 + w);
                }
            };
            for(auto [T, i] : st2[p1]) {
                ins(p2, T, i);
            }
            for(auto [S, i] : ed2[p1]) {
                ins(S, p2, i);
            }
        }
    }
    for(auto [qid, ans_, cost] : ans2) {
        ans[qid] = min(ans[qid], ans_ + cost);
    }
    for(int i = 0; i < q; i++) {
        cout << (ans[i] == inf ? -1 : ans[i]) << '\n';
    }
}
signed main() {
    atexit([](){cerr << "time: " << (db)clock()/CLOCKS_PER_SEC << "s\n";});
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    while(t--) solve();
    return 0;
}