// no matter how hard you work, someone else is working harder
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _i = (b); i <= _i; ++ i)
#define FORD(i, b, a) for (int i = (b), _i = (a); i >= _i; -- i)
#define REP(i, b) for (int i = 0, _i = (b); i < _i; ++ i)
#define FORE(i, a) for (auto& i : a)
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define cntbit __builtin_popcountll
#define len(x) (int)x.size()
#define bit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
template <typename A, typename B>
inline bool ckmax(A& a, const B& b) {
if (a < b) {
a = b;
return true;
} return false;
}
template <typename A, typename B>
inline bool ckmin(A& a, const B& b) {
if (a > b) {
a = b;
return true;
} return false;
}
inline void fileIO(const string& Task = "") {
ios::sync_with_stdio(false); cin.tie(NULL);
if (fopen((Task + ".inp").c_str(), "r")) {
freopen((Task + ".inp").c_str(), "r", stdin);
freopen((Task + ".out").c_str(), "w", stdout);
}
}
/* Author: Hoang Quoc Viet */
/** END OF TEMPLATE **/
int n, m, k, q;
int dp[80][80][80], cost[80][80][80], tmp[80][80];
int main() {
fileIO("main");
cin >> n >> m;
memset(cost, 0x3f, sizeof cost);
FOR(i, 1, n) cost[0][i][i] = cost[1][i][i] = 0;
FOR(i, 1, m) {
int u, v, t;
cin >> u >> v >> t;
ckmin(cost[1][u][v], t);
}
cin >> k >> q;
ckmin(k, n - 1);
FOR(i, 2, k) {
memset(tmp, 0x3f, sizeof tmp);
FOR(x, 1, n) FOR(y, 1, n) FOR(z, 1, n) {
ckmin(tmp[y][z], cost[i-1][y][x] + cost[1][x][z]);
}
FOR(y, 1, n) FOR(z, 1, n) {
cost[i][y][z] = min(cost[i-1][y][z], tmp[y][z]);
}
}
while (q --) {
int u, v;
cin >> u >> v;
if (cost[k][u][v] >= 1e9) cout << "-1\n";
else cout << cost[k][u][v] << "\n";
}
return 0;
}
/*** VOI VOI VOI important things must be said three times :> ***/
