#include <bits/stdc++.h> using namespace std; #define endl "\n" #define pb push_back // #define int long long #define fi first #define se second const int N = 74, M = 1e9 + 7, LG = 20; int n , A[N] , m , dis[N][N][N] , q , k , u , v , w; vector<pair<int,int>> lis[N]; void solve(){ for (int i=0 ; i<N ; i++){ for (int j=0 ; j<N ; j++){ for (int k=0 ; k<N ; k++){ dis[i][j][k] = 1e9; if (i==j){ dis[i][j][k] = 0; } } } } cin >> n >> m; map<pair<int,int> , int> wi; for (int i=1 ; i<=m ; i++){ cin >> u >> v >> w; if (wi[{u,v}] == 0){ wi[{u,v}] = w; continue; } wi[{u,v}] = min(wi[{u,v}] , w); } for (int i=1 ; i<=n ; i++){ for (int j=1 ; j<=n ; j++){ if (!wi[{i,j}]) continue; lis[i].pb({j , wi[{i,j}]}); } } for (int i=1 ; i<=n ; i++){ queue<pair<int,int>> qu; for (auto j : lis[i]){ qu.push(j); } for (int j=1 ; j<=n ; j++){ queue<pair<int,int>> tm; bool vi[N] = {}; while(qu.size()){ int v = qu.front().fi , di = qu.front().se; qu.pop(); dis[i][v][j] = min(dis[i][v][j] , di); // if (!vi[v]){ // vi[v] = 1; for (auto k : lis[v]){ tm.push({k.fi , k.se + di}); } // } } qu = tm; } } cin >> k >> q; k = min(k , n); while(q--){ cin >> u >> v; int ans = 1e9; for (int i=0 ; i<=k ; i++){ ans = min(ans , dis[u][v][i]); } if (ans == 1e9) ans = -1; cout << ans << endl; } } signed main(){ // freopen("" , "r" , stdin); // freopen("" , "w" , stdout); // cout << setprecision(30); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ts = 1; // cin >> ts; while(ts--){ solve(); } }