#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 75, INF = 0x3f3f3f3f3f3f3f3f;
// pair<int, int> dist[N][N];
int dist[N][N][N];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
memset(dist, 0x3f, sizeof dist);
while(m--){
int u, v, t;
cin >> u >> v >> t;
dist[u][v][1] = min(dist[u][v][1], t);
}
for(int i = 1; i <= n; ++i){
dist[i][i][0] = 0;
}
int k, q;
cin >> k >> q;
for(int x = 2; x <= min(k, n); ++x){
for(int l = 1; l <= n; ++l){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
dist[i][j][x] = min(dist[i][j][x], dist[i][l][x-1] + dist[l][j][1]);
}
}
}
}
while(q--){
int x, y;
cin >> x >> y;
int mn = INF;
for(int i = 0; i <= min(n, k); ++i) mn = min(mn, dist[x][y][i]);
cout << (mn == INF ? -1 : mn) << '\n';
}
}
