// 01001100 01001111 01010100 01000001 \\
// \\
// ╦ ╔═╗╔╦╗╔═╗ \\
// ║ ║ ║ ║ ╠═╣ \\
// ╩═╝╚═╝ ╩ ╩ ╩ \\
// \\
// 01001100 01001111 01010100 01000001 \\
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
const int N = 71;
int n;
int dp[N][N][N];
vector<pii> a[N];
void compute(int s){
int v, k, w;
for(int i = 1; i <= n; i++)
for(int j = 0; j < n; j++)
dp[s][i][j] = 1e9;
dp[s][s][0] = 0;
for(int i = 1; i <= n; i++)
dp[s][i][n] = 0;
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> Q;
Q.push({0, {0, s}});
while(!Q.empty()){
w = Q.top().ff;
v = Q.top().ss.ss;
k = Q.top().ss.ff;
Q.pop();
if(w == dp[s][v][k]){
for(auto & [i, j] : a[v]){
if(w + j < dp[s][i][k + 1]){
dp[s][i][k + 1] = w + j;
Q.push({w + j, {k + 1, i}});
}
}
}
}
}
void solve(){
int m, v, u, w, k, q, ans;
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> v >> u >> w;
a[v].append({u, w});
}
for(int i = 1; i <= n; i++)
compute(i);
cin >> k >> q;
k = min(k, n - 1);
while(q--){
cin >> v >> u;
ans = 1e9;
for(int i = 0; i <= k; i++)
ans = min(ans, dp[v][u][i]);
if(ans < 1e9) cout << ans << nl;
else cout << "-1\n";
}
}
int terminator(){
L0TA;
int T = 1;
//cin >> T;
while(T--)
solve();
return 0;
}
