#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9;

int n, m, dist[25000];
vector< pair<int, int> > g[25000];
bool mark[25000];

//queue
const int N = 100001;
int qdata[N], qnext[N], qhead[3], fr;

void push(int v, int x) {
    qdata[fr] = x;
    qnext[fr] = qhead[v];
    qhead[v] = fr;
    fr++;
}

void pop(int v) {
    qhead[v] = qnext[qhead[v]];
}

bool empty(int v) {
    return (qhead[v] == -1);
}

int front(int v) {
    return qdata[qhead[v]];
}


int solve(int s, int f) {
    fr = 0;
    qhead[0] = -1;
    qhead[1] = -1;
    qhead[2] = -1;

    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        mark[i] = false;
    }

    dist[s] = 0;
    push(0, s);
    while (!empty(0) || !empty(1) || !empty(2)) {
        int v = -1;
        if (!empty(0)) {
            v = front(0);
            pop(0);
        } else {
            swap(qhead[0], qhead[1]);
            swap(qhead[1], qhead[2]);
            continue;
        }
        if (mark[v] == true)
            continue;
        mark[v] = true;

        int x, y;
        x = dist[v] / 1000;
        for (int i = 0; i < (int)g[v].size(); i++) {
            int u = g[v][i].first;
            int w = g[v][i].second;
            if (dist[v] + w < dist[u]) {
                dist[u] = dist[v] + w;
                y = dist[u] / 1000;
                if (y - x == 1)
                    push(1, u);
                else
                    push(2, u);
            }
        }
    }
    if (dist[f] == INF)
        return -1;
    return dist[f];
}


int main() {
    scanf("%d%d", &n, &m);
    int x, y, w;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &x, &y, &w);
        x--; y--;
        g[x].push_back({y, w});
    }

    int k, s, f, ans;
    cin >> k;
    for (int i = 0; i < k; i++) {
        scanf("%d%d", &s, &f);
        s--; f--;
        ans = solve(s, f);
        printf("%d\n", ans);
    }
    return 0;
}