#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll
int k,n,m,q;
vector<vector<int>> roads[50005],rev[50005],query[200005];
int best[50005],ans[10005];
bool check[50005];
void update(int node, int l, int r, int a, int b, int ind){
int mid = (l+r)/2;
if(a/k<=mid and mid<=b/k){
query[node].push_back({a,b,ind});
}
else if(b/k<=mid){
update(node*2,l,mid,a,b,ind);
}
else{
update(node*2+1,mid+1,r,a,b,ind);
}
}
void walk(int node, int l, int r){
int mid = (l+r)/2;
if(l!=r){
walk(node*2,l,mid);
walk(node*2+1,mid+1,r);
}
int lef=l*k,rit=r*k+k-1;
for(int i=0;i<=k-1;i++){
for(int j=lef;j<=rit;j++){
best[j] = 2e9;
check[j] = false;
}
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
best[mid*k+i] = 0;
pq.push({0,mid*k+i});
while(pq.size()>0){
while(pq.size()>0 and check[pq.top()[1]]){
pq.pop();
}
if(pq.size()==0){
break;
}
int x = pq.top()[1];
pq.pop();
check[x] = true;
for(vector<int> j:roads[x]){
if(j[0]<=rit and best[x]+j[1]<best[j[0]]){
best[j[0]] = best[x]+j[1];
pq.push({best[j[0]],j[0]});
}
}
}
pq.push({0,mid*k+i});
check[mid*k+i] = false;
while(pq.size()>0){
while(pq.size()>0 and check[pq.top()[1]]){
pq.pop();
}
if(pq.size()==0){
break;
}
int x = pq.top()[1];
pq.pop();
check[x] = true;
for(vector<int> j:rev[x]){
if(j[0]>=lef and best[x]+j[1]<best[j[0]]){
best[j[0]] = best[x]+j[1];
pq.push({best[j[0]],j[0]});
}
}
}
for(vector<int> j:query[node]){
ans[j[2]] = min(ans[j[2]],best[j[0]]+best[j[1]]);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> k >> n >> m >> q;
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
roads[a].push_back({b,c});
rev[b].push_back({a,c});
}
for(int i=1;i<=q;i++){
int a,b;
cin >> a >> b;
update(1,0,n/k,a,b,i);
ans[i] = 2e9;
}
walk(1,0,n/k);
for(int i=1;i<=q;i++){
if(ans[i]==2e9){
cout << -1 << "\n";
}
else{
cout << ans[i] << "\n";
}
}
return 0;
}
