#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
#define int long long
const int inf = 1e18;
struct Matrix{
vector<vector<int>> v;
int r, c;
Matrix() = default;
Matrix(int R): Matrix(R, R) {
for (int i = 0; i < R; i++) v[i][i] = 0;
}
Matrix(int R, int C): r(R), c(C) {
v.assign(R, vector<int>(C, inf));
}
Matrix operator * (const Matrix &M){
Matrix res(r, M.c);
for (int i = 0; i < r; i++){
for (int k = 0; k < c; k++){
for (int j = 0; j < M.c; j++){
res.v[i][j] = min(res.v[i][j], v[i][k] + M.v[k][j]);
}
}
}
return res;
}
Matrix operator ^ (int a){
Matrix res(r);
for (Matrix exp = *this; a; a >>= 1, exp = exp * exp){
if (a & 1) res = res * exp;
}
return res;
}
};
void main_program(){
int n, m; cin >> n >> m;
Matrix mult(n);
for (int i = 0; i < m; i++){
int a, b, w; cin >> a >> b >> w;
a--; b--;
mult.v[a][b] = min(mult.v[a][b], w);
}
int k, q; cin >> k >> q;
mult = mult ^ k;
for (int qr = 0; qr < q; qr++){
int c, d; cin >> c >> d;
c--; d--;
Matrix base(1, n); base.v[0][c] = 0;
Matrix res = base * mult;
if (res.v[0][d] == inf) cout << "-1\n";
else cout << res.v[0][d] << "\n";
}
}
