# pragma GCC optimize("O3,unroll-loops")
# pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
# include <bits/stdc++.h>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
# define mkp make_pair
# define ff first
# define ss second
# define pll pair <ll, ll>
# define pii pair <int, int>
# define vec vector
# define pb push_back
# define pf push_front
# define ppb pop_back
# define ppf pop_front
# define all(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
# define sz(x) ((int)(x).size())
# define lb lower_bound
# define ub upper_bound
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
# define br break
# define rt return
# define cn continue
# define nl "\n"
# define off exit(0)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll MAXN = 1e6 + 25;
const ll MAXL = 18 + 0;
const ll INF1 = 1e18 + 0;
const ll INF2 = 2e9 + 0;
const ll MOD = 1e9 + 7;
const ll M0D = 998244353;
const ld PI = acos((ld) -1);
const ll P = 67 + 0 + 0;
using namespace std;
using namespace __gnu_pbds;
ll n, m, k, q;
ll g[75][75];
ll dp[75][75][75];
void ma1n ()
{
cin >> n >> m;
for (ll i = 0; i <= n; ++i)
{
for (ll j = 0; j <= n; ++j)
{
g[i][j] = INF1;
}
}
for (ll i = 1, u, v, w; i <= m; ++i)
{
cin >> u >> v >> w;
g[u][v] = min(g[u][v], w);
}
cin >> k >> q;
ll need = min(k, n);
for (ll cur = 0; cur <= need; ++cur)
{
for (ll i = 1; i <= n; ++i)
{
for (ll j = 1; j <= n; ++j)
{
dp[cur][i][j] = INF1;
dp[cur][i][i] = 0;
}
}
}
for (ll cur = 1; cur <= need; ++cur)
{
for (ll i = 1; i <= n; ++i)
{
for (ll j = 1; j <= n; ++j)
{
for (ll v = 1; v <= n; ++v)
{
dp[cur][i][j] = min(dp[cur][i][j], dp[cur - 1][i][v] + g[v][j]);
}
}
}
}
for (ll i = 1, u, v; i <= q; ++i)
{
cin >> u >> v;
cout << (dp[need][u][v] == INF1 ? -1 : dp[need][u][v]) << nl;
}
}
int main (/*?*/)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cerr.tie(0);
// freopen ("file.in", "r", stdin);
// freopen ("file.out", "w", stdout);
int zxc = 1;
// cin >> zxc;
while (zxc--)
{
ma1n();
}
return 0;
}
