#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
#define mins(a,b) (a = min(a,b))
const int MXN = 5e4+2, LOG = 16, MXK = 5, inf=1e9;
int k, n, m, q, rmq[LOG][MXN][MXK][MXK], ans[MXK][MXK], tmp[MXK][MXK];
vector<pii> g[MXN];
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
int m, q;
cin >> k >> n >> m >> q;
for(int i=0,u,v,w; i<m; i++) {
cin >> u >> v >> w;
g[u].push_back({v, w});
}
for(int i=0; i+1<=(n-1)/k; i++) {
for(int u=0; u<k; u++)
fill(rmq[0][i][u], rmq[0][i][u]+k, inf);
for(int u=i*k; u<(i+1)*k; u++)
for(auto [v, w] : g[u])
mins(rmq[0][i][u%k][v%k], w);
}
for(int i=1; i<LOG; i++)
for(int j=0; j+(1<<i)<=(n-1)/k; j++) {
for(int u=0; u<k; u++)
fill(rmq[i][j][u], rmq[i][j][u]+k, inf);
for(int u=0; u<k; u++)
for(int v=0; v<k; v++)
for(int w=0; w<k; w++)
mins(rmq[i][j][u][w], rmq[i-1][j][u][v] + rmq[i-1][j+(1<<(i-1))][v][w]);
}
for(int u=0; u<k; u++)
fill(tmp[u], tmp[u]+k, inf);
while(q--) {
int a, b;
cin >> a >> b;
int l = a/k, d = b/k-a/k;
if(d==0) {
cout << "-1\n";
continue;
}
bool fir=1;
while(d) {
int i = __lg(d&-d);
if(fir) {
for(int u=0; u<k; u++)
for(int v=0; v<k; v++)
ans[u][v] = rmq[i][l][u][v];
fir = 0;
}
else {
for(int u=0; u<k; u++)
for(int v=0; v<k; v++)
for(int w=0; w<k; w++)
mins(tmp[u][w], ans[u][v] + rmq[i][l][v][w]);
for(int u=0; u<k; u++)
for(int v=0; v<k; v++)
ans[u][v] = tmp[u][v],
tmp[u][v] = inf;
}
l += 1<<i;
d ^= 1<<i;
}
int res = ans[a%k][b%k];
cout << (res==inf ? -1 : res) << '\n';
}
return 0;
}
