#include<bits/stdc++.h>
using namespace std;
long long n, m, road[71][71], mi[71][71][71], inf=1e12;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("autobus.inp", "r", stdin);
//freopen("autobus.out", "w", stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)road[i][j]=0;
else {
road[i][j]=inf;
}
mi[i][j][0]=road[i][j];
}
}
for(int o=1;o<=m;o++){
long long a, b, v;
cin>>a>>b>>v;
road[a][b]=min(road[a][b], v);
mi[a][b][1]=road[a][b];
}
for(int k=1;k<n;k++){///toi da di dc n-1 thanh pho
for(int i=1;i<=n;i++){///thanh pho di
for(int j=1;j<=n;j++){///thanh pho den
mi[i][j][k]=mi[i][j][k-1];
for(int h=1;h<=n;h++)mi[i][j][k]=min(mi[i][j][k], mi[i][h][k-1]+road[h][j]);///i->j or i->h->j
}
}
}
long long k, q;
cin>>k>>q;
k=min(k, n-1);
for(int i=1;i<=q;i++){
long long a, b;
cin>>a>>b;
if(mi[a][b][k]<inf)cout<<mi[a][b][k]<<"\n";
else cout<<"-1\n";
}
return 0;
}
