#include <bits/stdc++.h>
using namespace std;
const int N = 75, INF = 1e9;
int n, m, k, q, dp[N][N][N];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) for(int k = 0;k<=n;k++) dp[i][j][k] = INF;
for(int i = 1;i<=n;i++) dp[i][i][0] = 0;
for(int i = 1;i<=m;i++){
int u, v, w; cin >> u >> v >> w;
dp[u][v][1] = min(dp[u][v][1], w);
}
cin >> k >> q;
for(int l = 1;l<=min(n, k);l++){
for(int k = 1;k<=n;k++){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
for(int f = 0;f<=l;f++){
dp[i][j][l] = min(dp[i][j][l], dp[i][k][f] + dp[k][j][l - f]);
}
dp[i][j][l] = min(dp[i][j][l], dp[i][j][l - 1]);
}
}
}
}
while(q--){
int u, v;
cin >> u >> v;
cout << (dp[u][v][min(n, k)] == INF ? -1 : dp[u][v][min(n, k)]) << '\n';
}
}
