#include<bits/stdc++.h>
//#define int long long
#define inf 1e9
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define TASKNAME "Toll"
using namespace std;
template<typename T> bool minimize(T &a, T b){ if (a > b) {a = b; return true; } return false; }
struct matrix{
vector<vector<int>> mat;
int r, c;
matrix(int _r = 0, int _c = 0){
r = _r, c = _c;
mat.resize(_r, vector<int>(_c, inf));
}
void print(){
FOR(i, 0, r - 1){
FOR(j, 0, c - 1){
printf("%lld ", mat[i][j]);
}
printf("\n");
}
}
};
matrix mul(matrix a, matrix b){
matrix res(a.r, b.c);;
FOR(i, 0, a.r - 1){
FOR(j, 0, b.c - 1){
FOR(k, 0, a.c - 1){
minimize(res.mat[i][j], a.mat[i][k] + b.mat[k][j]);
}
}
}
return res;
}
const int MAXN = 5e4 + 9;
int n, m, q, k;
vector<matrix> transD;
matrix P[20][MAXN];
int mask[MAXN];
void DnC(int l, int r, int lvl){
if (l == r) return;
int mid = (l + r) >> 1;
FOR(i, l, r) P[lvl][i] = matrix(k, k);
P[lvl][mid] = transD[mid];
P[lvl][mid + 1] = transD[mid + 1];
//
FORD(i, mid - 1, l) P[lvl][i] = mul(transD[i], P[lvl][i + 1]);
FOR(i, mid + 2, r) P[lvl][i] = mul(P[lvl][i - 1], transD[i]);
FOR(i, mid + 1, r) mask[i] ^= (1LL << lvl);
DnC(l, mid, lvl + 1);
DnC(mid + 1, r, lvl + 1);
}
matrix Query(int l, int r){
if (l == r) return transD[l];
else {
int bit = __builtin_ctz(mask[l] ^ mask[r]);
//// printf("%lld %lld\n", l, r);
// P[bit][l].print();
// P[bit][r].print();
return mul(P[bit][l], P[bit][r]);
}
}
void solve(){
cin >> k >> n >> m >> q;
transD.resize(n / k + 9, matrix(k, k));
FOR(i, 0, m - 1){
int u, v, t;
cin >> u >> v >> t;
minimize(transD[u / k].mat[u % k][v % k], t);
}
// FOR(i, 0, n / k - 1){
// FOR(j, 0, k - 1){
// FOR(t, 0, k - 1){
// printf("%lld ", transD[i].mat[j][t]);
// }
// printf("\n");
// }
// printf("\n");
// }
//transD[i]: ma tran de chuyen tu block i len block i + 1.
DnC(0, n / k - 1, 0);
// Query(0, 3).print();
FOR(i, 0, q - 1){
int u, v;
cin >> u >> v;
if (u / k == v / k) printf("-1\n");
else{
matrix start(k, k);
start.mat[u % k][u % k] = 0;
start = mul(start, Query(u / k, v / k - 1));
// start.print();
// printf("%lld %lld\n", u / k, v / k - 1);
// Query(u / k, v / k - 1).print();
if (start.mat[u % k][v % k] < inf) {
printf("%lld\n", start.mat[u % k][v % k]);
}
else printf("-1\n");
}
}
}
main(){
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
solve();
}
