#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<set<pair<int, int>>> g(n);
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        g[u].emplace(v, w);
        g[v].emplace(u, w);
    }
    set<pair<int, int>> s;
    for (int i = 0; i < n; i++) {
        s.emplace(g[i].size(), i);
    }
    while (!s.empty()) {
        auto [_, u] = *s.begin();
        s.erase(s.begin());
        for (auto [v, w] : g[u]) {
            s.erase({g[v].size(), v});
            g[v].erase({u, w});
            s.emplace(g[v].size(), v);
        }
    }
    int q;
    cin >> q;
    vector<int> res(q, INT_MAX);
    vector<tuple<int, int, int, int>> qs;
    vector<vector<tuple<int, int, int, int>>> q1(n), q2(n);
    vector<gp_hash_table<int, int>> mp(n);
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        s--, t--;
        qs.emplace_back(s, t, i, 0);
    }
    auto rec = [&](auto self, int k, vector<tuple<int, int, int, int>> qs) -> void {
        if (k == 1) {
            for (int i = 0; i < n; i++) {
                mp[i].clear();
            }
            for (int i = 0; i < n; i++) {
                for (auto [j, w] : g[i]) {
                    mp[i][j] = mp[j][i] = w;
                }
            }
            for (auto [s, t, id, inc] : qs) {
                if (mp[s].find(t) != mp[s].end()) {
                    res[id] = min(res[id], mp[s][t] + inc);
                }
            }
        } else if (k == 2) {
            for (int i = 0; i < n; i++) {
                mp[i].clear();
            }
            for (int i = 0; i < n; i++) {
                for (auto [j, w] : g[i]) {
                    mp[i][j] = mp[j][i] = w;
                }
            }
            vector<tuple<int, int, int, int>> nqs;
            for (auto [s, t, id, inc] : qs) {
                for (auto [x, w] : g[s]) {
                    if (mp[x].find(t) != mp[x].end()) {
                        res[id] = min(res[id], mp[x][t] + inc + w);
                    }
                }
                for (auto [x, w] : g[t]) {
                    if (mp[s].find(x) != mp[s].end()) {
                        res[id] = min(res[id], mp[s][x] + inc + w);
                    }
                }
            }
            self(self, k - 1, nqs);
            for (int i = 0; i < n; i++) {
                mp[i].clear();
            }
            vector<int> pre(qs.size(), -1), best(qs.size(), INT_MAX);
            for (int i = 0; i < qs.size(); i++) {
                auto [s, t, id, inc] = qs[i];
                if (mp[s].find(t) == mp[s].end()) {
                    mp[s][t] = i;
                } else {
                    pre[i] = mp[s][t];
                }
            }
            for (int i = 0; i < n; i++) {
                for (auto [j, w1] : g[i]) {
                    for (auto [k, w2] : g[i]) {
                        if (mp[j].find(k) != mp[j].end()) {
                            int id = mp[j][k];
                            best[id] = min(best[id], w1 + w2);
                        }
                    }
                }
            }
            for (int i = 0; i < qs.size(); i++) {
                if (pre[i] != -1) {
                    best[i] = best[pre[i]];
                }
                if (best[i] != INT_MAX) {
                    auto [s, t, id, inc] = qs[i];
                    res[id] = min(res[id], best[i] + inc);
                }
            }
        } else if (k == 3) {
            vector<tuple<int, int, int, int>> nqs;
            for (auto [s, t, id, inc] : qs) {
                for (auto [x, w] : g[s]) {
                    nqs.emplace_back(x, t, id, inc + w);
                }
                for (auto [x, w] : g[t]) {
                    nqs.emplace_back(s, x, id, inc + w);
                }
            }
            self(self, k - 1, nqs);
            for (int i = 0; i < n; i++) {
                mp[i].clear();
            }
            vector<int> pre(qs.size(), -1), best(qs.size(), INT_MAX);
            for (int i = 0; i < qs.size(); i++) {
                auto [s, t, id, inc] = qs[i];
                if (mp[s].find(t) == mp[s].end()) {
                    mp[s][t] = i;
                } else {
                    pre[i] = mp[s][t];
                }
            }
            for (int i = 0; i < n; i++) {
                for (auto [j, w1] : g[i]) {
                    for (auto [k, w2] : g[i]) {
                        for (auto [l, w3] : g[j]) {
                            if (mp[k].find(l) == mp[k].end()) {
                                int id = mp[k][l];
                                best[id] = min(best[id], w1 + w2 + w3);
                            }
                            if (mp[l].find(k) == mp[l].end()) {
                                int id = mp[l][k];
                                best[id] = min(best[id], w1 + w2 + w3);
                            }
                        }
                    }
                }
            }
            for (int i = 0; i < qs.size(); i++) {
                if (pre[i] != -1) {
                    best[i] = best[pre[i]];
                }
                if (best[i] != INT_MAX) {
                    auto [s, t, id, inc] = qs[i];
                    res[id] = min(res[id], best[i] + inc);
                }
            }
        }
    };
    rec(rec, 1, qs);
    rec(rec, 2, qs);
    rec(rec, 3, qs);
    for (int x : res) {
        cout << (x == INT_MAX ? -1 : x) << "\n";
    }
    return 0;
}