#include <bits/stdc++.h>
using namespace std;
const int MK = 5;
const int MX = 5e4 + 10;
const int INF = 1e9 + 7;
int K, N, M, Q;
void chmin(int& a, int b){
if(b < a) a = b;
}
struct matrix{
int arr[MK][MK];
void init(int t = INF){
for(int i = 0; i < K; i++){
for(int j = 0; j < K; j++) arr[i][j] = INF;
arr[i][i] = t;
}
}
matrix operator + (const matrix& other){
matrix c; c.init();
for(int i = 0; i < K; i++){
for(int j = 0; j < K; j++){
for(int k = 0; k < K; k++){
chmin(c.arr[i][j], arr[i][k] + other.arr[k][j]);
}
}
}
return c;
}
};
matrix A[MX];
struct segtree{
matrix st[MX << 1];
void build(){
for(int i = MX; i < (MX << 1); i++) st[i] = A[i - MX];
for(int i = MX - 1; i > 0; i--) st[i] = st[i << 1] + st[i << 1|1];
}
matrix que(int l, int r){
matrix lf, rg; lf.init(0); rg.init(0);
for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
if(l & 1) lf = lf + st[l], l++;
if(r & 1) --r, rg = st[r] + rg;
}
lf = lf + rg;
return lf;
}
} S;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> K >> N >> M >> Q;
for(int i = 0; i < (N - 1) / K; i++) A[i].init();
for(int i = 0; i < M; i++){
int a, b, t; cin >> a >> b >> t;
chmin(A[a / K].arr[a % K][b % K], t);
}
S.build();
for(int i = 0; i < Q; i++){
int a, b; cin >> a >> b;
if(a / K == b / K){
cout << -1 << '\n';
continue;
}
matrix ans = S.que(a / K, b / K - 1);
if(ans.arr[a % K][b % K] == INF) cout << -1 << '\n';
else cout << ans.arr[a % K][b % K] << '\n';
}
}
