#include <iostream>
#include <climits>
using namespace std;
int dist[401][401], numberOfNodes, numberOfEdges;

void init() {
    int from, to, weight;

    //scanf("%d %d", &numberOfNodes, &numberOfEdges);

    for (int i = 1; i <= numberOfNodes; i++) {
        for (int j = 1; j <= numberOfNodes; j++) {
            dist[i][j] = INT_MAX;
        }
        dist[i][i] = 0;
    }

    for (int i = 0; i < numberOfEdges; i++) {
        //scanf("%d %d %d", &from, &to, &weight);
        cin >> from >> to >> weight;
        dist[from][to] = weight;
    }
}

void floyd() {
    for (int k = 1; k <= numberOfNodes; k++) {
        for (int i = 1; i <= numberOfNodes; i++) {
            for (int j = 1; j <= numberOfNodes; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}
void printArray() {
    for (size_t i = 1; i <= numberOfNodes; i++)
    {
        for (size_t j = 1; j <= numberOfNodes; j++)
        {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}
int main() {
    cin >> numberOfNodes >> numberOfEdges;
    init();
    floyd();
    int queries;
    cin >> queries;
    for (int i = 0; i < queries; i++) {
        int first, second;
        cin >> first >> second;
        if (dist[first][second] == INT_MAX) {
            cout << -1;
        }
        else {
            cout << dist[first][second];
        }
        cout << endl;
    }
    //printArray();
}