//In the name of God
#include<bits/stdc++.h>
#define lc (id * 2)
#define rc (id * 2 + 1)
#define md ((s + e) / 2)
#define dm ((s + e) / 2 + 1)
#define ln (e - s + 1)
using namespace std;
typedef long long ll;
const ll MXN = 5e4 + 10;
const ll MXS = MXN * 4;
const ll MXZ = 10;
const ll INF = 1e10;
struct Matrix{
ll n, m;
ll M[MXZ][MXZ];
Matrix(ll _n = 0, ll _m = 0, ll f = 0){
n = _n, m = _m;
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
if(f == -1) M[i][j] = (i == j ? 0 : INF);
else M[i][j] = f;
}
}
}
void Print(){
cout << "======= N.N =======\n";
for(int i = 0; i < n; i ++, cout << '\n'){
for(int j = 0; j < m; j ++) cout << M[i][j] << ' ';
}
cout << "======= N.N =======\n";
}
Matrix operator * (const Matrix &T){
assert(m == T.n);
Matrix R = Matrix(n, T.m, INF);
for(int i = 0; i < n; i ++){
for(int k = 0; k < m; k ++){
for(int j = 0; j < T.m; j ++){
R.M[i][j] = min(R.M[i][j], M[i][k] + T.M[k][j]);
}
}
}
return R;
}
};
ll k, n, m, q;
ll ANS[MXN];
vector<pair<ll, ll>> adj[MXN], adt[MXN], Q[MXN];
Matrix seg[MXS], Now, Res, lz, base[MXZ];
void Build(ll id = 1, ll s = 1, ll e = n){
seg[id] = Matrix(k, k, -1);
if(ln > 1){
Build(lc, s, md), Build(rc, dm, e);
}
}
void Set(ll p, ll id = 1, ll s = 1, ll e = n){
if(e < p || s > p) return;
if(ln == 1){
seg[id] = Now; return;
}
Set(p, lc, s, md), Set(p, rc, dm, e);
//seg[id] = seg[lc] * seg[rc];
seg[id] = seg[rc] * seg[lc];
}
void fetch(ll l, ll r, ll id = 1, ll s = 1, ll e = n){
if(e < l || s > r) return;
if(l <= s && e <= r){
//lz = lz * seg[id];
lz = seg[id] * lz;
return;
}
fetch(l, r, lc, s, md), fetch(l, r, rc, dm, e);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> k >> n >> m >> q;
for(int i = 0; i < m; i ++){
ll u, v, w; cin >> u >> v >> w;
u ++, v ++;
adj[u].push_back({v, w});
adt[v].push_back({u, w});
}
for(int i = 0; i < q; i ++){
ll u, v; cin >> u >> v; u ++, v ++;
Q[v].push_back({u, i});
}
Build();
for(int i = 0; i < k; i ++) base[i] = Matrix(k, 1, INF), base[i].M[i][0] = 0;
for(int f = 0; f <= (n - 1) / k; f ++){
ll s = f * k + 1, e = min((f + 1) * k, n);
if(f){
Now = Matrix(k, k, INF);
for(int v = s; v <= e; v ++){
for(auto X : adt[v]){
ll u, w; tie(u, w) = X;
ll vp = (v - 1) % k, up = (u - 1) % k;
Now.M[vp][up] = min(Now.M[vp][up], w);
}
}
Set(s - 1);
}
for(int v = s; v <= e; v ++){
for(auto X : Q[v]){
ll u, id; tie(u, id) = X;
Res = base[(u - 1) % k];
lz = Matrix(k, k, -1); fetch(u, n);
Res = lz * Res;
ANS[id] = Res.M[(v - 1) % k][0];
}
}
}
for(int i = 0; i < q; i ++) cout << (ANS[i] == INF ? -1 : ANS[i]) << '\n';
//cout << "Ok\n";
return 0;
}
//! This is NIMA !
