#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <fstream>
#include <climits>
#include <algorithm>
#include <cstring> // Для memset
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
const LL DIM = 50007;
const LL INF = INT_MAX;
LL n, k, o, m, v1, v2, t;
class edge {
public:
LL to, w;
edge(LL to_, LL w_) {
to = to_;
w = w_;
}
};
vector < edge > v[DIM];
class tran {
public:
LL** mat;
tran() {
mat = new LL* [k];
for (int i = 0; i < k; i++) {
mat[i] = new LL[k];
for (int j = 0; j < k; j++) {
mat[i][j] = INF;
}
}
}
~tran() {
for (int i = 0; i < k; i++) {
delete[] mat[i];
}
delete[] mat;
}
};
tran solve(LL L, LL R) {
tran ans;
if (R - L == 1) {
for (int i = 0; i < k; i++) {
LL val = L * k + i;
for (auto to : v[val]) {
ans.mat[i][to.to - (R * k)] = to.w;
}
}
return ans;
}
LL mid = (L + R) / 2;
tran m1 = solve(L, mid);
tran m2 = solve(mid, R);
for (int l = 0; l < k; l++) {
for (int r = 0; r < k; r++) {
for (int m = 0; m < k; m++) {
ans.mat[l][r] = min(ans.mat[l][r], m1.mat[l][m] + m2.mat[m][r]);
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> k >> n >> m >> o;
for (int i = 1; i <= m; i++) {
cin >> v1 >> v2 >> t;
v[v1].push_back({ v2, t });
}
vector<LL> out;
for (int i = 1; i <= o; i++) {
cin >> v1 >> v2;
if (v1 / k >= v2 / k || m == 0) {
out.push_back(-1);
}
else {
tran res = solve(v1/ k, v2 / k);
LL result = res.mat[v1 - (v1 / k) * k][v2 - (v2 / k) * k];
if (result >= INF) cout << -1 << endl;
cout << result << endl;
}
}
return 0;
}
