#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int k,n,m;
int l;
const ll inf=10000000000000000;
vector<vector<pair<int,ll>>> adj;
vector<vector<pair<int,ll>>> radj;
vector<vector<vector<ll>>> dd;
void dv(int lt, int rt, int lv){
int bl=lt/k;
int br=rt/k;
if(bl>=br){
return;
}
int tm=(bl+br)/2;
int ps=tm*k;
int pse=ps+k-1;
for(int i=0;i<k;i++){
dd[lv][ps+i][i]=0;
for(int j=pse+1;j<=rt;j++){
for(auto p:radj[j]){
if(p.first>=ps+i and dd[lv][p.first][i]!=inf){
dd[lv][j][i]=min(dd[lv][j][i],dd[lv][p.first][i]+p.second);
}
}
}
for(int j=ps-1;j>=lt;j--){
for(auto p:adj[j]){
if(p.first<=ps+i and dd[lv][p.first][i]!=inf){
dd[lv][j][i]=min(dd[lv][j][i],dd[lv][p.first][i]+p.second);
}
}
}
}
dv(lt,ps-1,lv+1);dv(pse+1,rt,lv+1);
}
ll qu(int tl, int tr, int lt, int rt, int lv){
int btl=tl/k;
int btr=tr/k;
int blt=lt/k;
int brt=rt/k;
if(btl<=blt and btr>=brt){
if(blt==brt){
if(lt!=rt)return -1;
return 0;
}
ll ans=inf;
int tm=(btl+btr)/2;
int ps=tm*k;
int pse=ps+k-1;
for(int i=0;i<k;i++){
ans=min(ans,dd[lv][lt][i]+dd[lv][rt][i]);
}
if(ans==inf)return -1;
return ans;
}
int tm=(btl+btr)/2;
int ps=tm*k;
int pse=ps+k-1;
if(blt>tm)return qu(pse+1,tr,lt,rt,lv+1);
return qu(tl,ps-1,lt,rt,lv+1);
}
int main(){
int o;
cin >> k >> n>> m >> o;
adj.resize(n);
radj.resize(n);
for(int i=0;i<m;i++){
int a,b;
ll t;
cin >> a>> b >> t;
adj[a].push_back({b,t});
radj[b].push_back({a,t});
}
l=ceil(log2(n));
dd.resize(l+1,vector<vector<ll>>(n,vector<ll>(k,inf)));
dv(0,n-1,0);
while(o--){
int lt,rt;
cin >> lt >> rt;
cout << qu(0,n-1,lt,rt,0) << "\n";
}
}
