#include <bits/stdc++.h>
using namespace std;
#define pll pair<int, int>
#define int long long
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
const int blk=200;
int n,o,k,m;
vector<vector<int>> fw(50005, vector<int>(5, 1e12));
vector<int> dist(50005, 1e12);
vector<vector<pair<int,int>>> in(50005);
void pass(int sl, int el){
for(int i=sl+1;i<=el;i++){ // reset.
for(int j=0;j<k;j++){
int cn=i*k+j;
dist[cn]=1e12;
for(auto [f, c]:in[cn]){
dist[cn]=min(dist[cn], dist[f]+c);
}
}
}
}
signed main(){
//~ cin.tie(0);
cin>>k>>n>>m>>o;
for(int i=0;i<m;i++){
int a,b,t;cin>>a>>b>>t;
in[b].pb({a, t});
}
for(int i=0;i<n;i++){
// calc distances after forwarding 200 .
// reset dist of current layer.
int sl=i/k;
for(int j=0;j<k;j++){
int cn=sl*k+j;
dist[cn]=1e12;
}
dist[i]=0;
pass(sl, sl+blk);
int el=sl+blk;
for(int j=0;j<k;j++){
int cn=el*k+j;
fw[i][j]=dist[cn];
}
}
while(o--){
int a,b;cin>>a>>b;
vector<int> layer(k, 1e12); layer[a%k]=0;
int cl=a/k, el=b/k;
while(el - cl >= blk){
vector<int> nxt(k, 1e12);
for(int i=0;i<k;i++){
int cn=cl*k+i;
for(int j=0;j<k;j++){
nxt[j]=min(nxt[j], layer[i]+fw[cn][j]);
}
}
swap(layer, nxt);
cl+=blk;
}
for(int i=0;i<k;i++){
dist[cl*k+i]=layer[i];
}
pass(cl, el);
if(dist[b] >= 1e12)cout<<-1<<"\n";
else cout<<dist[b]<<"\n";
}
}
