#include<bits/stdc++.h>
#define int long long
using namespace std;
int inf=1e12;
int k,n,m,o;
pair<int,int>g(int x){
int d=x/k+1;
int r=x%k;
return {d,r};
}
struct mat{
int info[6][6];
mat(int v=inf){
for(int i=0;i<5;i++)for(int j=0;j<5;j++)info[i][j]=v;
}
friend mat operator+(mat a,mat b){
mat c(inf);
for(int i=0;i<5;i++)for(int j=0;j<5;j++)for(int k=0;k<5;k++){
c.info[i][k]=min(c.info[i][k],a.info[i][j]+b.info[j][k]);
}
return c;
}
}temp[50005];
struct segtree{
mat info[50005];
void build(int st,int en,int i){
if(st==en)return info[i]=temp[st],void();
int m=(st+en)/2;
build(st,m,i*2);
build(m+1,en,i*2+1);
info[i]=info[i*2]+info[i*2+1];
}
mat fans(int st,int en,int i,int l,int r){
if(st>=l&&en<=r)return info[i];
int m=(st+en)/2;
if(r<=m)return fans(st,m,i*2,l,r);
else if(l>=m+1)return fans(m+1,en,i*2+1,l,r);
return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
}
}tr;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>k>>n>>m>>o;
int N=n/k+1;
for(int i=0;i<m;i++){
int a,b,t;cin>>a>>b>>t;
auto aa=g(a);
auto bb=g(b);
temp[aa.first].info[aa.second][bb.second]=t;
}
//cerr<<"work\n";
tr.build(1,N,1);
//cerr<<"work\n";
for(int i=0;i<o;i++){
int a,b;cin>>a>>b;
auto aa=g(a);
auto bb=g(b);
if(aa.first==bb.first){
cout<<"-1\n";
}else{
//cerr<<aa.first<<' '<<aa.second<<" "<<bb.first<<" "<<bb.second<<"\n";
auto temp=tr.fans(1,N,1,aa.first,bb.first-1);
int ans=temp.info[aa.second][bb.second];
if(ans>=inf)cout<<"-1\n";
else cout<<ans<<"\n";
}
}
}
