#include <bits/stdc++.h>
using namespace std;
const int N = 70 + 5, INF = 1e9 + 5;
int n, m, a, b, c, k, q, dist[N][N][N];
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
for(int k = 0; k < N; k++){
dist[i][j][k] = INF;
}
}
}
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> a >> b >> c;
dist[1][a][b] = min(dist[1][a][b], c);
}
for(int i = 1; i <= n; i++) dist[1][i][i] = 0;
for(int i = 2; i <= n; i++){
for(int a = 1; a <= n; a++){
for(int b = 1; b <= n; b++){
dist[i][a][b] = dist[i - 1][a][b];
for(int v = 1; v <= n; v++){
dist[i][a][b] = min(dist[i][a][b], dist[i - 1][a][v] + dist[1][v][b]);
}
}
}
}
cin >> k >> q;
while(q--){
cin >> a >> b;
cout << (dist[min(n, k)][a][b] == INF ? -1 : dist[min(n, k)][a][b]) << "\n";
}
}
