#include <bits/stdc++.h> using namespace std; const int inf = 1e9; signed main() { ios::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); int n,m; cin>>n>>m; int nei[n+1][n+1]; vector<vector<int>> dis(n+1,vector<int>(n+1)); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) nei[i][j]=dis[i][j]=(i!=j)*inf; for (int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; nei[a][b]=min(nei[a][b],c); } int k,q; cin>>k>>q; k=min(k,n-1); for (int i=0;i<k;i++) { vector<vector<int>> dis1=dis; for (int i=1;i<=n;i++) for (int p=1;p<=n;p++) for (int j=1;j<=n;j++) dis1[i][j]=min(dis1[i][j],nei[i][p]+dis[p][j]); dis=dis1; } while (q--) { int a,b; cin>>a>>b; cout<<(dis[a][b]<inf?dis[a][b]:-1)<<endl; } return 0; }