#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+5, MXK = 5, inf=1e9;
int k;
struct node {
int dis[MXK][MXK];
node() {
for(int i=0; i<MXK; i++)
fill(dis[i], dis[i]+MXK, inf);
}
};
node *seg[MXN<<2];
node *merge(node *x, node *y) {
node *z = new node();
for(int i=0; i<k; i++)
for(int j=0; j<k; j++)
for(int l=0; l<k; l++)
mins(z->dis[i][l], x->dis[i][j] + y->dis[j][l]);
return z;
}
int n;
vector<pii> g[MXN];
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
void build(int l=0, int r=(n-1)/k, int id=1) {
if(r-l==0) return;
if(r-l==1) {
seg[id] = new node();
for(int i=l*k; i<(l+1)*k && i<n; i++)
for(auto [j, w] : g[i])
mins(seg[id]->dis[i%k][j%k], w);
return;
}
build(l, mid, lc);
build(mid, r, rc);
seg[id] = merge(seg[lc], seg[rc]);
}
node *get(int s, int e, int l=0, int r=(n-1)/k, int id=1) {
if(r-l==0) return seg[0];
if(s<=l && r<=e) return seg[id];
if(e<=mid) return get(s, e, l, mid, lc);
if(s>=mid) return get(s, e, mid, r, rc);
return merge(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}
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});
}
seg[0] = new node();
build();
while(q--) {
int a, b;
cin >> a >> b;
if(a/k==b/k) cout << "-1\n";
int ans = get(a/k, b/k)->dis[a%k][b%k];
cout << (ans==inf ? -1 : ans) << '\n';
}
return 0;
}
