#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Edge {
int x, y, t;
Edge(int xi, int yi, int ti):x(xi),y(yi),t(ti){}
};
struct Path {
int i, c;
Path(int ii, int ci):i(ii),c(ci){}
};
bool compare(Path a, Path b) {
return a.c < b.i;
}
int k, n, m, q, x, y, t;
vector<vector<Edge>> graph;
signed main() {
cin >> k >> n >> m >> q;
graph = vector<vector<Edge>>(n);
for(int i = 0; i < m; i++) {
cin >> x >> y >> t;
graph[x].push_back(Edge(x, y, t));
}
while(q--) {
// djikstra from a to b
cin >> x >> y;
priority_queue<Path, vector<Path>, function<bool(Path, Path)>> pq(compare);
vector<int> dist(n, LLONG_MAX);
Path temp(0,0);
pq.push(Path(x, 0));
while(pq.size()) {
temp = pq.top();
pq.pop();
if(dist[temp.i] < temp.c) continue;
dist[temp.i] = temp.c;
for(auto j : graph[temp.i]) {
if(temp.c + j.t < dist[j.y]) pq.push(Path(j.y, temp.c + j.t));
}
}
if(dist[y] == LLONG_MAX) cout << "-1\n";
else cout << dist[y] << "\n";
}
}
