#include <bits/stdc++.h>
using namespace std;
int const INF=1e9;
int const MAX=5e4+5;
int const LOG=18;
int k,n,m,q;
int dist[MAX][LOG][5];
void read(){
cin>>k>>n>>m>>q;
int i;
for(i=1;i<=m;++i){
int u,v,w;
cin>>u>>v>>w;
dist[u][0][v%k]=w;
}
}
void minself(int& x,int val){
if(x>val)
x=val;
}
void precalc(){
int i,j,rest,inter;
for(i=0;i<n;++i)
for(j=0;j<LOG;++j)
for(rest=0;rest<k;++rest)
if(!dist[i][j][rest])
dist[i][j][rest]=INF;
for(j=1;j<LOG;++j)
for(i=0;i<n;++i)
for(rest=0;rest<k;++rest)
for(inter=0;inter<k;++inter)
if(i/k*k+k*(1<<(j-1))+inter<n)
minself(dist[i][j][rest],dist[i][j-1][inter]+dist[i/k*k+k*(1<<(j-1))+inter][j-1][rest]);
}
int solve(int u,int v){
int hu=u/k;
int hv=v/k;
int difh=hv-hu;
vector<int>nodes(k);
vector<int>dst(k);
int i;
for(i=0;i<k;++i){
nodes[i]=u/k*k+i;
if(u==nodes[i])
dst[i]=0;
else
dst[i]=INF;
}
int bit;
for(bit=0;(1<<bit)<=difh;++bit)
if(difh&(1<<bit)){
vector<int>new_nodes(k);
vector<int>new_dst(k);
int rest,inter;
for(rest=0;rest<k;++rest){
new_nodes[rest]=nodes[rest]+k*(1<<bit);
new_dst[rest]=INF;
}
for(rest=0;rest<k;++rest)
for(inter=0;inter<k;++inter)
minself(new_dst[rest],dst[inter]+dist[nodes[inter]][bit][rest]);
for(rest=0;rest<k;++rest){
nodes[rest]=new_nodes[rest];
dst[rest]=new_dst[rest];
}
}
if(dst[v%k]<INF)
return dst[v%k];
return -1;
}
void process_queries(){
int i;
for(i=1;i<=q;++i){
int u,v;
cin>>u>>v;
cout<<solve(u,v)<<'\n';
}
}
int main()
{
read();
precalc();
process_queries();
return 0;
}
