#include <bits/stdc++.h> using namespace std; const int N=72; vector<pair<int,int>> ma[N]; 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 i=0;i<m;i++) { int a,b,t; cin>>a>>b>>t; ma[a].push_back({b,t}); } for(int start=1;start<=n;start++) { priority_queue<vector<int>> pq; for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { dp[start][j][i]=1e9*(j!=start); } pq.push({0,start,i}); } while(pq.size()>0) { auto it=pq.top(); pq.pop(); int x=it[1]; int d=it[0]; int k=it[2]; if(dp[start][x][k]!=d)continue; if(k==n)continue; for(auto it:ma[x]) { int y=it.first,w=it.second; if(dp[start][y][k+1]>d+w) { dp[start][y][k+1]=d+w; pq.push({d+w,y,k+1}); } } } } int k,q; cin>>k>>q; 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; } }