#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 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;
#define mid ((l+r)/2)
int n,m,k,o;
vii adj[MAXN], revadj[MAXN];
int cev[MAXN], bb[MAXN], dist[MAXN];
void dij(int bas,int l,int r){
priority_queue<pii,vii,greater<pii>> pq;
FOR(i,n) dist[i]=INF;
dist[bas]=0;
pq.push({0,bas});
while(!pq.empty()){
auto el=pq.top();
pq.pop();
int d=el.fi;
int nd=el.se;
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;
pq.push({dist[kom],kom});
}
}
}
pq.push({0,bas});
while(!pq.empty()){
auto el=pq.top();
pq.pop();
int d=el.fi;
int nd=el.se;
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;
pq.push({dist[kom],kom});
}
}
}
}
void solve(int l,int r,vector<pair<pii,int>>& qq){
if(l>r or qq.empty()) return;
for(int i=mid*k;i<min(mid*k+k,n);i++){
dij(i,l,r);
for(auto el:qq){
int bas=el.fi.fi;
int son=el.fi.se;
int ind=el.se;
if(bb[bas]<=mid and mid<=bb[son]) cev[ind]=min(cev[ind],dist[bas]+dist[son]);
}
}
vector<pair<pii,int>> sag,sol;
for(auto el:qq){
if(bb[el.fi.se]<mid) sol.pb(el);
if(bb[el.fi.fi]>mid) sag.pb(el);
}
solve(l,mid,sol);
solve(mid+1,r,sag);
}
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;
FORE(i,1,o+1) cev[i]=INF;
vector<pair<pii,int>> qq;
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;
}
