#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define NMOD 3
#define ll long long
#define fi first
#define se second
#define pb push_back
#define log 17
#define mask(i) (1ll << (i))
#define setp(x) setprecision(x)
#define ALL(v) v.begin(), v.end()
#define ck(n, i) (((n) >> (i)) & 1)
#define getbit(x) __builtin_popcount(x)
const double PI = acos(-1);
const long long MOD = 1e9 + 7;
const long long MOD1 = 998244353;
const long long MODo = 123456789;
const int oo = 1e9;
const long long oo15 = 1e15, oo18 = 1e18+3, oooo = 922372036854775807;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DATA
{
int st, tt, len;
bool operator < (const DATA &o) const
{
return len > o.len;
}
};
int dist[72][72][72], low[77][77];
vector<pair<int,int>> a[72];
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
low[i][j] = oo;
for (int e = 0; e <= n; e++)
dist[i][j][e] = oo;
}
for (int i = 1; i <= m; i++)
{
int u, v, t;
cin >> u >> v >> t;
low[u][v] = min(low[u][v], t);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (low[i][j] < oo)
{
a[i].pb({j, low[i][j]});
}
int k, q;
cin >> k >> q;
k = min(k, n);
for (int st = 1; st <= n; st++)
{
priority_queue<DATA> qe;
dist[st][st][0] = 0;
qe.push({st, 0, 0});
// cout << st << endl;
while(!qe.empty())
{
int u = qe.top().st, tt = qe.top().tt, len = qe.top().len; qe.pop();
// cout << u << " " << tt << " " << len << endl;
if (dist[st][u][tt] != len || tt == k) continue;
for (auto v : a[u])
if (dist[st][v.fi][tt + 1] > len + v.se)
{
dist[st][v.fi][tt + 1] = len + v.se;
if (tt + 1 < k)
qe.push({v.fi, tt + 1, dist[st][v.fi][tt + 1]});
}
}
}
while(q--)
{
int u, v;
cin >> u >> v;
int ans = oo;
for (int i = 0; i <= k; i++) ans = min(ans, dist[u][v][i]);
if (ans == oo) cout << "-1\n"; else cout << ans << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int testcase = 1;
//cin >> testcase;
while(testcase--)
solve();
}
