#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 50005
int dp[MAXN][LOGN][5][5];
void merge(int q[5][5], int a[5][5], int b[5][5]) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
q[i][j] = min(q[i][j], a[i][k] + b[k][j]);
}
}
}
}
int main() {
fast
int K, N, M, O;
cin >> K >> N >> M >> O;
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < LOGN; j++)
for (int k = 0; k < 5; k++)
for (int l = 0; l < 5; l++)
dp[i][j][k][l] = 1e9;
for (int i = 0; i < M; i++) {
int a, b, c;
cin >> a >> b >> c;
dp[a/K][0][a%K][b%K] = c;
}
for (int i = 1; i < LOGN; i++) {
for (int j = 0; j + (1<<i) - 1 < MAXN; j++) {
merge(dp[j][i], dp[j][i-1], dp[j+(1<<(i-1))][i-1]);
}
}
while (O--) {
int a, b;
cin >> a >> b;
int h1 = a/K;
int h2 = b/K;
int n1 = a%K;
int n2 = b%K;
vector<int> ans(5, 1e9);
ans[n1] = 0;
for (int i = LOGN-1; i >= 0; i--) {
if (h1 + (1<<i) <= h2) {
vector<int> new_ans(5, 1e9);
for (int old_rem = 0; old_rem < K; old_rem++) {
for (int rem = 0; rem < K; rem++) {
new_ans[rem] = min(new_ans[rem], ans[old_rem] + dp[h1][i][old_rem][rem]);
}
}
ans = new_ans;
h1 += (1<<i);
}
}
cout << (ans[n2] >= 1e9 ? -1 : ans[n2]) << "\n";
}
}
