#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 <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 = 999999999999;
LL n, k, o, m;
class edge {
public:
LL to, w;
};
vector < edge > v[DIM];
class tran {
public:
LL mat[5][5];
void init() {
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
mat[i][j] = INF;
}
}
}
};
tran solve(LL L, LL R) {
tran ans;
ans.init();
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++) {
LL a, b, t;
cin >> a >> b >> t;
v[a].push_back({ b, t });
}
for (int i = 1; i <= o; i++) {
LL a, b;
cin >> a >> b;
LL b1 = a / k;
LL b2 = b / k;
if (b1 >= b2) cout << -1 << endl;
else {
LL res = solve(b1, b2).mat[a - b1 * k][b - b2 * k];
if (res >= INF) cout << -1;
else cout << res;
cout << endl;
}
}
return 0;
}
