#include <iostream>
using namespace std;
const int N = 75;
int Mn[N][N], dp[N][N][N], n, m, K, q;
int 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++){
Mn[i][j] = 1e9 * (i != j);
for (int k=0;k<=n;k++)
dp[i][j][k] = Mn[i][j];
}
}
for (int i=1;i<=m;i++){
int a, b, t;
cin>>a>>b>>t;
Mn[a][b] = min(Mn[a][b], t);
}
for (int k=1;k<=n;k++){
for (int l=1;l<=n;l++){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++)
dp[i][j][k] = min(dp[i][j][k], dp[i][l][k-1] + Mn[l][j]);
}
}
}
cin>>K>>q;
K = min(n, K);
for (int i=1;i<=q;i++){
int a, b;
cin>>a>>b;
if (dp[a][b][K] == 1e9)
dp[a][b][K] = -1;
cout<<dp[a][b][K]<<'\n';
}
}
