#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 75;
//vector< pair<int, int> > g[N];
int n, m, q, k, F;
bool used[N];
ll dst[N][N][N], g[N][N];
/*
void dfs(int v, int skok, ll sum)
{
if (skok > k || sum > ans) return;
if (v == F)
{
ans = min(ans, sum);
return;
}
for(auto [u, w] : g[v])
{
dfs(u, skok + 1, sum + w);
}
}
*/
void calc(int x)
{
for(int i = 1; i <= n; i++)
for(int j = 0; j <= k; j++)
dst[x][i][j] = 1e18;
dst[x][x][0] = 0;
set< pair<ll, pair<int, int> > > se;
se.insert({0, {0, x}});
while(sz(se) > 0)
{
auto c = *se.begin(); se.erase(se.begin());
ll d = c.fi;
int v = c.sd.sd, skok = c.sd.fi;
if (dst[x][v][skok] < d) continue;
for(int u = 1; u <= n; u++)
{
if (g[v][u] == 1e18) continue;
ll w = g[v][u];
if (skok + 1 <= k && dst[x][v][skok] + w < dst[x][u][skok + 1])
{
dst[x][u][skok + 1] = dst[x][v][skok] + w;
se.insert({dst[x][u][skok + 1], {skok + 1, u}});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
g[i][j] = 1e18;
for(int i = 1; i <= m; i++)
{
int u, v;
ll z;
cin >> u >> v >> z;
g[u][v] = min(g[u][v], z);
}
cin >> k >> q;
k = min(k, n);
for(int i = 1; i <= n; i++)
calc(i);
while(q--)
{
int S;
cin >> S >> F;
ll ans = 1e18;
for(int i = 0; i <= k; i++) ans = min(ans, dst[S][F][i]);
if (ans == 1e18) cout << -1 << '\n';
else cout << ans << '\n';
}
}
