#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll N=5e4+5,inf=1e18;
ll n,m,k,q,ans[N],dis[5][N];
vector<pll> adj_pos[N],adj_opp[N];
vector<pair<pll,ll> > QQ;
ll left(ll x){return x*k;}
ll right(ll x){return x*k+k-1;}
ll ID(ll x){return x/k;}
void dij(ll start,vector<pll> *adj,ll *dis,ll L,ll R){
rep(i,L,R) dis[i]=inf;
dis[start]=0;
priority_queue<pll,vector<pll>,greater<pll> > pq;
pq.push(mp(0,start));
while(!pq.empty()){
ll u=pq.top().ss,cost=pq.top().ff;pq.pop();
if(cost>dis[u]) continue;
for(auto o:adj[u]){
ll v=o.ff,w=o.ss;
if(!(L<=v&&v<=R)) continue;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
pq.push(mp(dis[v],v));
}
}
}
}
void DC(ll l,ll r,vector<pair<pll,ll> > &qry){
if(l==r){
for(auto o:qry){
ll L=o.ff.ff,R=o.ff.ss,id=o.ss;
ans[id]=-1;
}
return ;
}
ll mid=(l+r)>>1;
rep(i,left(mid),right(mid)){
dij(i,adj_opp,dis[i-left(mid)],left(l),right(mid-1));
dij(i,adj_pos,dis[i-left(mid)],left(mid+1),right(r));
}
vector<pair<pll,ll> > lft,rgt;
for(auto o:qry){
ll L=o.ff.ff,R=o.ff.ss,id=o.ss;
if(ID(L)>mid) rgt.push_back(o);
else if(ID(R)<=mid) lft.push_back(o);
else{
ans[id]=inf;
rep(i,0,4) ans[id]=min(ans[id],dis[i][L]+dis[i][R]);
if(ans[id]==inf) ans[id]=-1;
}
}
vector<pair<pll,ll> >().swap(qry);
DC(l,mid,lft);
DC(mid+1,r,rgt);
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>k>>n>>m>>q;
rep(i,1,m){
ll u,v,w;
cin>>u>>v>>w;
adj_pos[u].push_back(mp(v,w));
adj_opp[v].push_back(mp(u,w));
}
rep(i,1,q){
ll u,v;
cin>>u>>v;
QQ.push_back(mp(mp(u,v),i));
}
DC(0,n/k,QQ);
rep(i,1,q) cout<<ans[i]<<'\n';
return 0;
}
