#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=1e10+5;;
int k,n,m,o;
vii adj[MAXN];
int deg[MAXN];
map<int,int> dist[MAXN];
void dfs(int nd,int d,int bas){
if(dist[nd][bas]==0) dist[nd][bas]=d;
else dist[nd][bas]=min(dist[nd][bas],d);
//dist[nd][bas]=d; //bastan bana mesafe
for(auto el:adj[nd]){
int kom=el.fi;
int cost=el.se;
dfs(kom,d+cost,bas);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//there is only one path from a to b
cin>>k>>n>>m>>o;
FOR(i,m){
int a,b,t;
cin>>a>>b>>t;
a++;b++;
adj[a].pb({b,t});
deg[b]++;
}
FORE(i,1,n+1){
if(deg[i]==0){
dfs(i,1,i);
}
}
while(o--){
int a,b;
cin>>a>>b;
a++;b++;
int cev=INF;
for(auto el:dist[a]){
int bas=el.fi;
int cost=el.se;
if(dist[b][bas]==0) continue;
if(cost>dist[b][bas]) continue;
cev=min(cev,dist[b][bas]-cost);
}
cout<<(cev==INF?-1:cev)<<endl;
}
}
