#include <bits/stdc++.h> using namespace std; #define int long long int const N=72; vector<pair<int,int>>nei[N]={}; int dp[N][N]={}; int ans[N][N]; int n,m; int lm; void bfs(int s) { for (int i=1;i<=n;i++) for (int j=0;j<=n;j++) dp[i][j]=1e12; dp[s][0]=0; priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>pq; pq.push({0,0,s}); while (pq.size()) { vector<int>f=pq.top(); pq.pop(); int u=f[2],w=f[0],k=f[1]; if (dp[u][k]!=w) continue; for (auto [i,w1]:nei[u]) { if (k+1<=lm&&dp[i][k+1]>w+w1) { dp[i][k+1]=w+w1; pq.push({dp[i][k+1],k+1,i}); } } } for (int i=1;i<=n;i++) { int mn=1e18; for (int j=0;j<=n;j++) { mn=min(mn,dp[i][j]); } if (mn==1e12) continue; ans[s][i]=mn; } } inline void solve() { cin>>n>>m; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { dp[i][j]=1e12; ans[i][j]=-1; } dp[i][i]=0; ans[i][i]=0; } for (int i=0;i<m;i++) { int a,b,t; cin>>a>>b>>t; dp[a][b]=min(dp[a][b],t); } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (dp[i][j]!=1e12&&dp[i][j]) nei[i].push_back({j,dp[i][j]}); } } int k,q; cin>>k>>q; lm=k; lm=min(lm,n); for (int i=1;i<=n;i++) bfs(i); while (q--) { int a,b; cin>>a>>b; cout<<ans[a][b]<<'\n'; } } signed main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int t=1; for (int i=1;i<=t;i++) { solve(); } }