// #include <bits/stdc++.h> #include <iostream> #include <vector> #include <queue> 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 , wi[N][N]; 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; 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<int> qu; queue<int> tm; for (auto j : lis[i]){ qu.push(j.fi); dis[i][j.fi][1] = j.se; } for (int j=1 ; j<=n ; j++){ if (j&1){ while(qu.size()){ int v = qu.front() , di = dis[i][v][j]; qu.pop(); for (auto k : lis[v]){ tm.push(k.fi); dis[i][k.fi][j+1] = min(dis[i][k.fi][j+1] , k.se + di); } } }else{ while(tm.size()){ int v = tm.front() , di = dis[i][v][j]; tm.pop(); for (auto k : lis[v]){ qu.push(k.fi); dis[i][k.fi][j+1] = min(dis[i][k.fi][j+1] , k.se + di); } } } } } 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(); } }