#include <bits/stdc++.h>
typedef long long int ll;
const ll inf = 1e18;
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll n, m;
cin >> n >> m;
vector<array<ll, 3>> edge(m);
for(auto &[u, v, w] : edge)
cin >> u >> v >> w, --u, --v;
ll val[n][n];
for(ll i = 0; i < n; i++)
for(ll j = 0; j < n; j++)
val[i][j] = inf;
for(auto [u, v, w] : edge)
val[u][v] = min(val[u][v], w);
ll k, q;
cin >> k >> q;
if(k > n - 1)
k = n - 1;
ll dp[k + 1][n][n];
for(ll l = 0; l <= k; l++)
for(ll i = 0; i < n; i++)
for(ll j = 0; j < n; j++)
dp[l][i][j] = inf;
for(ll i = 0; i < n; i++)
dp[0][i][i] = 0;
for(ll l = 1; l <= k; l++)
for(ll v = 0; v < n; v++)
for(ll i = 0; i < n; i++)
for(ll j = 0; j < n; j++)
if(dp[l - 1][i][v] != inf && edge[v][j] != inf)
dp[l][i][j] = min(dp[l][i][j], dp[l - 1][i][v] + val[v][j]);
while(q--){
ll u, v, ans = inf;
cin >> u >> v; --u; --v;
for(ll l = 0; l <= k; l++)
ans = min(ans, dp[l][u][v]);
cout << (ans != inf ? ans : -1) << "\n";
}
}
