#include <bits/stdc++.h>
#define SPED \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen
#define Data tuple<lint, int, int>
const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;
using namespace std;
int n, m;
lint adj[75][75], dist[75][75][75]; // dist[s][k][t] (s to t, k diffrent roads, shortest way)
void dijkstra(int z, lint DIST[][75])
{
DIST[0][z] = 0;
priority_queue<Data, vector<Data>, greater<Data>> pq;
pq.emplace(0, 0, z);
while (!pq.empty())
{
auto [du, k, u] = pq.top();
pq.pop();
if (du > DIST[k][u])
continue;
for (int i = 1; i <= n; i++)
if (i != u)
if (DIST[k + 1][i] > DIST[k][u] + adj[u][i] and k + 1 <= n)
{
DIST[k + 1][i] = DIST[k][u] + adj[u][i];
pq.emplace(DIST[k + 1][i], k + 1, i);
}
}
}
fami lore()
{
SPED;
memset(adj, 0x1f, sizeof adj);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int l, r;
lint w;
cin >> l >> r >> w;
adj[l][r] = min(adj[l][r], w); // có hướng
}
memset(dist, 0x1f, sizeof dist);
for (int i = 1; i <= n; i++)
dijkstra(i, dist[i]);
for (int i = 1; i <= n; i++)
for (int l = 1; l <= n; l++)
for (int r = 1; r <= n; r++)
dist[l][i][r] = min(dist[l][i][r], dist[l][i - 1][r]);
int k, q;
cin >> k >> q;
k = min(k, n);
while (q--)
{
int l, r;
cin >> l >> r;
cout << (dist[l][k][r] == INF ? -1 : dist[l][k][r]) << endl;
}
}
// Let your soul wander where dreams are born.
