#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'; } }