#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<
#define pb push_back
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define cont(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
#define DEBUG(x) cout<<#x sp ":" sp x<<endl;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;
//#define mid (l+r)/2
#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
#define carp(x,y) ((x%MOD)*(y%+MOD))%MOD
const int MAXN=5e4+5;
const int INF=1e18;;
int k,n,m,o;
vii adj[MAXN], revadj[MAXN];
int bb[MAXN], cev[MAXN], dist[MAXN];
void dij(int bas,int l,int r){
//bas bloğundan itibaren [l-r] aralığına shortest path at
FOR(i,n) dist[i]=INF;
priority_queue<pii, vii, greater<pii>> q;
q.push({0,bas});
dist[bas]=0;
while(!q.empty()){
auto el=q.top();
q.pop();
int nd=el.se;
int d=el.fi;
for(auto [kom,cost]:adj[nd]){
if(bb[kom]<l or bb[kom]>r) continue;
if(dist[nd]+cost<dist[kom]){
dist[kom]=dist[nd]+cost;
q.push({dist[kom],kom});
}
}
}
q.push({0,bas});
while(!q.empty()){
auto el=q.top();
q.pop();
int nd=el.se;
int d=el.fi;
for(auto [kom,cost]:revadj[nd]){
if(bb[kom]<l or bb[kom]>r) continue;
if(dist[nd]+cost<dist[kom]){
dist[kom]=dist[nd]+cost;
q.push({dist[kom],kom});
}
}
}
}
void solve(int a,int b,vector<pair<pii,int>>& qq){
if(a>b or qq.empty()) return;
int mid=(a+b)/2; //ikisinin de geçmek zorunda olduğu blok
//i'nin bloğu--> i/k
//i'nin bloğundaki elemanlar --> [i*k,i*(k+1)-1];
for(int i=k*mid;i<min(n,k*mid+k);i++){ //bu bloktaki her elemandan shortest path at
dij(i,a,b);
for(auto el:qq){
int bas=el.fi.fi;
int son=el.fi.se;
int ind=el.se;
if(bb[bas]<=mid and bb[son]>=mid){
//querynin ayrıldığı kısım
cev[ind]=min(cev[ind],dist[bas]+dist[son]);
}
}
}
vector<pair<pii,int>> l,r;
for(auto el:qq){ //queryler midin neresinde kalıyor
if(bb[el.fi.se]<mid) l.pb(el);
if(bb[el.fi.fi]>mid) r.pb(el);
}
solve(a,mid,l);
solve(mid+1,b,r);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>k>>n>>m>>o;
FOR(i,m){
int a,b,t;
cin>>a>>b>>t;
adj[a].pb({b,t});
revadj[b].pb({a,t});
}
FOR(i,n) bb[i]=i/k;
vector<pair<pii,int>> qq;
FORE(i,1,o+1) cev[i]=INF;
int say=1;
while(o--){
int a,b;
cin>>a>>b;
qq.pb({{a,b},say++});
}
solve(0,bb[n-1],qq);
FORE(i,1,say) cout<<(cev[i]>=INF?-1:cev[i])<<endl;
}
