#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double
const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 74;
int dp[MAXN][MAXN][MAXN];
int adj[MAXN][MAXN];
vector<pair<int, int>> dest[MAXN];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int n, m;
cin>>n>>m;
clr(adj, -1);
for(int i= 0;i<m;i++){
int t1, t2, t3;
cin>>t1>>t2>>t3;
if(adj[t1][t2] == -1){
adj[t1][t2] = t3;
} else {
adj[t1][t2] = min(adj[t1][t2], t3);
}
}
for(int i= 1;i<=n;i++){
for(int j= 1;j<=n;j++){
if(adj[j][i] != -1){
dest[i].pb({j, adj[j][i]});
}
}
}
int q, K;
cin>>K>>q;
clr(dp, -1);
for(int i = 1;i<=n;i++){
dp[i][i][0] = 0;
for(int j= 1;j<=n;j++){
dp[i][j][1] = adj[i][j];
}
dp[i][i][1] = 0;
}
for(int k = 2;k<=min(n+1, K);k++){
for(int i = 1;i<=n;i++){
for(int j= 1;j<=n;j++){
if(i == j) {
dp[i][j][k] = 0;
continue;
}
dp[i][j][k] = INF;
for(auto x: dest[j]){
if(dp[i][x.fr][k-1] == -1) continue;
dp[i][j][k] = min(dp[i][j][k], dp[i][x.fr][k-1]+x.sc);
}
if(dp[i][j][k] == INF){
dp[i][j][k] = -1;
}
}
}
}
while(q--){
int t1, t2;
cin>>t1>>t2;
int ans = INF;
for(int i= 1;i<=min(n+1, K);i++){
if(dp[t1][t2][i] == -1) continue;
ans = min(ans, dp[t1][t2][i]);
}
if(ans == INF) ans = -1;
cout<<ans<<endl;
}
return 0;
}
// At most 70*70 bus routes
// q = 70*70
// DP[i][j][k] = min(DP[i][a][x] + DP[b][j][k-x] + T(ab))
// dp[i][j][k] = min(dp[i][a][k-1] + T(aj))
