#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define ll long long
int n, m, q, k;
ll adjm[75][75];
ll memo[75][75][75];
ll dp(ll d, ll x, ll y){
if(x == y) return 0;
if(d <= 0) return 1000000000000;
if(memo[d][x][y] != -1) return memo[d][x][y];
ll minn = 1000000000000;
for(int i = 1; i <= n; i++){
minn = min(minn, dp(d - 1, x, i) + adjm[i][y]);
}
return memo[d][x][y] = minn;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(memo, -1, sizeof(memo));
cin >> n >> m;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
adjm[i][j] = 1000000000000;
if(i == j) adjm[i][j] = 0;
}
}
for(int i = 0; i < m; i++){
ll a, b, t; cin >> a >> b >> t;
adjm[a][b] = min(adjm[a][b], t);
}
cin >> k >> q;
k = min(k, n - 1);
for(int i = 0; i < q; i++){
ll c, d; cin >> c >> d;
ll ans = dp(k, c, d);
if(ans == 1000000000000) ans = -1;
cout << ans << endl;
}
}
