#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sz(v) v.size()
#define up_b upper_bound
#define low_b lower_bound
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=5e4+11;
const ll mod=1e9+7;
const int inf=1e9;
int k,n,m,o;
int lef[5][N],rig[5][N];
vector<pair<int,int>>g[N][2];
int ans[N];
int A[N],B[N];
void go(int l,int r,vector<int>orders){
if(l==r){
for(int i:orders){
ans[i]=inf;
}
return ;
}
int mid=(l+r)/2;
for(int x=0;x<k;x++){
for(int i=l*k;i<(r+1)*k;i++){
lef[x][i]=inf;
rig[x][i]=inf;
}
lef[x][mid*k+x]=0;
rig[x][mid*k+x]=0;
for(int i=(mid+1)*k;i<(r+1)*k;i++){
for(pair<int,int>p:g[i][1]){
rig[x][i]=min(rig[x][i],rig[x][p.x]+p.y);
}
}
for(int i=mid*k-1;i>=l*k;i--){
for(pair<int,int>p:g[i][0]){
lef[x][i]=min(lef[x][i],lef[x][p.x]+p.y);
}
}
}
vector<int>todo[2];
for(int i:orders){
int a=A[i],b=B[i];
if(a/k<=mid&&mid<b/k){
ans[i]=inf;
for(int x=0;x<k;x++){
ans[i]=min(ans[i],lef[x][a]+rig[x][b]);
}
continue;
}
todo[a/k>mid].pb(i);
}
go(l,mid,todo[0]);
go(mid+1,r,todo[1]);
}
void solve() {
cin>>k>>n>>m>>o;
for(int i=1;i<=m;i++){
int a,b,t;
cin>>a>>b>>t;
g[a][0].pb(mp(b,t));
g[b][1].pb(mp(a,t));
}
vector<int>orders;
for(int i=0;i<o;i++){
cin>>A[i]>>B[i];
orders.pb(i);
}
go(0,(n-1)/k,orders);
for(int i=0;i<o;i++){
if(ans[i]==inf)ans[i]=-1;
cout<<ans[i]<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--){
solve();
cout<<"\n";
}
}
