#include <bits/stdc++.h>
using namespace std;
const int INF = 500000001;
const int MAX_N = 50000;
struct Matrix {
int matr[5][5];
Matrix() {
for(int i = 0; i < 5; ++i)
for(int j = 0; j < 5; ++j)
matr[i][j] = INF;
}
};
Matrix mergeMatrices(int k, Matrix a, Matrix b) {
Matrix rez;
for(int i = 0; i < k; ++i)
for(int j = 0; j < k; ++j)
for(int l = 0; l < k; ++l)
rez.matr[i][j] = min(rez.matr[i][j], a.matr[i][l] + b.matr[l][j]);
return rez;
}
Matrix aint[1+4*MAX_N];
Matrix tranz[MAX_N];
void init(int K, int nod = 1, int l = 0, int r = MAX_N - 1) {
if(l < r) {
int mid = (l + r) / 2;
init(K, 2 * nod, l, mid);
init(K, 2 * nod + 1, mid + 1, r);
aint[nod] = mergeMatrices(K, aint[2 * nod], aint[2 * nod + 1]);
} else {
aint[nod] = tranz[l];
}
}
Matrix query(int K, int i, int j, int l = 0, int r = MAX_N - 1, int nod = 1) {
if(i <= l && r <= j) {
return aint[nod];
} else {
int mid = (l + r) / 2;
Matrix rez;
if(i <= mid) {
rez = query(K, i, j, l, mid, 2 * nod);
if(j > mid)
rez = mergeMatrices(K, rez, query(K, i, j, mid + 1, r, 2 * nod + 1));
} else
rez = query(K, i, j, mid + 1, r, 2 * nod + 1);
return rez;
}
}
int main() {
int K, N, M, O;
scanf("%d%d%d%d", &K, &N, &M, &O);
for(int i = 0; i < M; ++i) {
int a, b, t;
scanf("%d%d%d", &a, &b, &t);
tranz[a / K].matr[a % K][b % K] = min(tranz[a / K].matr[a % K][b % K], t);
}
init(K);
for(int i = 0; i < O; ++i) {
int a, b;
scanf("%d%d", &a, &b);
if(a / K >= b / K)
printf("-1\n");
else {
Matrix rez = query(K, a / K, b / K - 1);
if(rez.matr[a % K][b % K] >= INF)
printf("-1\n");
else
printf("%d\n", rez.matr[a % K][b % K]);
}
}
return 0;
}
