#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define z third
#define pb push_back
#define ins insert
#define len(x) (int) x.size()
#define all(a) a.begin(), a.end()

#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define tests() int T; cin >> T; for (int TTT = 0; TTT < T; ++TTT)
#define read(a) for (int i = 0; i < a.size(); ++i) cin >> a[i];
#define print(x, text) cout << text << " = " << x << endl;
#define printv(x, text) cout << text << " = "; for (auto e : x) cout << e << ' '; cout << endl;
#define printvp(x, text) cout << text << " =\n"; for (auto e : x) cout << e.first << ' ' << e.second << endl; cout << endl;

typedef long long ll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef pair <int, int> pii;

int n, m;
vector < vector <pii> > a;

void bfs(int st, int fin) {
    vector <int> dist(n, -1);
    vector <bool> used(n, 0);
    dist[st] = 0;
    used[st] = 1;

    queue <int> q[3];
    //q[0].clear(); q[1].clear(); q[2].clear();
    q[0].push(st);

    int num = 0;
    while (!q[num].empty()) {
        int v = q[num].front();
        q[num].pop();
        used[v] = 0;

        for (auto e : a[v]) {
            int u = e.x, w = e.y;
            if (dist[u] == -1 || dist[u] > dist[v] + w) {
                dist[u] = dist[v] + w;
                int next = dist[u] / 1000 % 3;
                if (!used[u]) {
                    q[next].push(u);
                    used[u] = 1;
                }
            }
        }

        for (int i = 0; q[num].empty() && i < 3; ++i)
            num = (num + 1) % 3;
    }

    cout << dist[fin] << "\n";
}

int main() {
    fast_io;

    cin >> n >> m;

    a.resize(n);
    //map <pii, int> mw;
    for (int i = 0; i < m; ++i) {
        int v, u, w;
        cin >> v >> u >> w;
        v--, u--;
        if (v == u) continue;
        //if (mw.count({v, u}) == 0) mw[{v, u}] = 1e9;
        //mw[{v, u}] = min(mw[{v, u}], w);
    //}
    //for (auto e : mw) {
        //int v = e.x.x, u = e.x.y, w = e.y;
        a[v].pb({u, w});
    }

    tests() {
        int v, u;
        cin >> v >> u;
        bfs(v - 1, u - 1);
    }
}