#include <bits/stdc++.h> using namespace std; const int N=72; int dp[N][N][N]; int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dp[i][j][k]=1e9*(i!=j); } } } for(int i=0;i<m;i++) { int a,b,t; cin>>a>>b>>t; dp[a][b][1]=min(dp[a][b][1],t); } for(int k=2;k<=n;k++) { for(int m=1;m<=n;m++) { for(int s=1;s<=n;s++) { for(int e=1;e<=n;e++) { dp[s][e][k]=min(dp[s][e][k],dp[s][m][k-1]+dp[m][e][1]); dp[s][e][k]=min(dp[s][e][k],dp[s][m][1]+dp[m][e][k-1]); } } } } int k,q; cin>>k>>q; k=min(k,n); while(q--) { int c,d; cin>>c>>d; if(dp[c][d][k]==1e9)dp[c][d][k]=-1; cout<<dp[c][d][k]<<endl; } }