#include <bits/stdc++.h>
const int N = 75;
int G[N][N], dp[N][N][N];
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int n, m;
	memset(G, 0x3f, sizeof G);
	memset(dp, 0x3f, sizeof dp);
	std::cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y, w;
		std::cin >> x >> y >> w;
		G[x][y] = std::min(G[x][y], w);
	}
	for (int i = 1; i <= n; ++i) dp[0][i][i] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int x = 1; x <= n; ++x)
			for (int y = 1; y <= n; ++y) {
				dp[i][x][y] = dp[i - 1][x][y];
				for (int z = 1; z <= n; ++z)
					dp[i][x][y] = std::min(dp[i][x][y], dp[i - 1][x][z] + G[z][y]);
			}
	}
	int k, q;
	std::cin >> k >> q;
	k = std::min(k, n);
	while (q--) {
		int x, y;
		std::cin >> x >> y;
		if (dp[k][x][y] >= 0x3f3f3f3f) {
			std::cout << -1 << '\n';
		}
		else {
			std::cout << dp[k][x][y] << '\n';
		}
	}
}