// Only GOD
// Believe in yourself!
// -o Sango zadam be shishe
// -o Comeback bezan hamishe!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
#define pb push_back
#define F first
#define S second
#define bit(x, y) (x >> y)&1
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define mid ((l+r)>>1)
#define lid (id << 1)
#define rid (lid | 1)
const int N = 5e4+10;
const int INF = 1e9+10;
int n, m, k, o;
vector<pii> query[N];
vector<pii> G[N];
int ans[N], dis[N];
set<int> s;
void dij(int v){
priority_queue<pii> q;
for(int i=0; i <= n; i++)
dis[i] = INF;
dis[v] = 0;
q.push({0, v});
while(!q.empty()){
int a=q.top().S;
q.pop();
for(auto x : G[a]){
if(dis[a] + x.S < dis[x.F]){
dis[x.F] = dis[a] + x.S;
q.push({-dis[x.F], x.F});
}
}
}
}
int32_t main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> k >> n >> m >> o;
for(int i = 0; i < m; i++){
int v, u, w;
cin >> v >> u >> w;
G[v].pb({u, w});
}
for(int i =1 ; i <= o; i++){
int v, u;
cin >> v >> u;
query[v].pb({u, i});
s.insert(v);
}
for(int u:s){
dij(u);
for(auto x : query[u]){
ans[x.S] = dis[x.F];
}
}
for(int i = 1;i <= o; i++)
cout << (ans[i] == INF ? -1 : ans[i]) << '\n';
}
