#include<bits/stdc++.h>

using namespace std;

#define FOR(i, mx) for(int i = 0; i < mx; i++)

void floyd(int A, vector<vector<int>>& vt){
    for(int k = 0; k < A; k++)
        for(int i = 0; i < A; i++)
            for(int j = 0; j < A; j++){
                vt[i][j] = vt[j][i] = max(vt[i][j], min(vt[i][k], vt[k][j]));
            }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int A, B, C;
    while (true){
        cin >> A >> B;
        if(A == 0 && B == 0) break;
        vector<vector<int>> vt (A, vector<int> (A, 0));
        FOR(i, B){
            int i1, i2, i3;
            cin >> i1 >> i2 >> i3;
            i1--; i2--;
            vt[i1][i2] = vt[i2][i1] = max(i3, vt[i1][i2]);
        }
        floyd(A, vt);
        
        cin >> C;
        FOR(i,C){
            int i1, i2;
            cin >> i1 >> i2;
            i1--; i2--;
            cout << vt[i1][i2] << "\n";
        }
    }
}