#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e10;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int k,n,m,q;
cin >> k >> n >> m >> q;
auto combine = [&](vector<vector<int>> DPa,vector<vector<int>> DPb){
vector DPres(k,vector(k,INF));
for(int l=0;l<k;l++){
for(int r=0;r<k;r++){
for(int x=0;x<k;x++){
DPres[l][r]=min(DPres[l][r],DPa[l][x]+DPb[x][r]);
}
}
}
return DPres;
};
int totBlocks = n/k;
vector lift(totBlocks+1,vector(16,vector(k,vector(k,INF))));
for(int i=1;i<=m;i++){
int a,b,t;cin>>a>>b>>t;
int block = a/k;
a%=k;b%=k;
lift[block][0][a][b]=t;
}
for(int bit=1;bit<16;bit++){
for(int i=0;i<=totBlocks;i++){
if(i+(1<<bit)>totBlocks)continue;
lift[i][bit]=combine(lift[i][bit-1],lift[i+(1<<(bit-1))][bit-1]);
}
}
for(int i=1;i<=q;i++){
int a,b;cin>>a>>b;
int blockA = a/k;a%=k;
int blockB = b/k;b%=k;
int tar = blockB-blockA;
vector res(k,vector(k,INF));
for(int j=0;j<k;j++)res[j][j]=0;
for(int bit=0;bit<16;bit++)if(tar&(1<<bit)){
res=combine(res,lift[blockA][bit]);
blockA+=(1<<bit);
}
if(res[a][b]>=INF)cout<<"-1\n";
else cout<<res[a][b]<<'\n';
}
}
