#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
ll k, n, m, o, dp[50050];
vvii adj;
void getToll(ll u) {
//cerr << "// getToll(" << u << ", " << v << ")\n";
if (dp[u] != -1) return;
//if (u == 1) cerr << "// check1\n";
ll minToll = 1e10;
for (ii edge : adj[u]) {
//if (u == 1) cerr << "// check2 {" << edge.fi << ", " << edge.se << "}\n";
getToll(edge.fi);
ll currToll = dp[edge.fi] + edge.se;
if (currToll < minToll) minToll = currToll;
}
dp[u] = minToll;
//cerr << "// " << dp[u] << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n >> m >> o;
adj.assign(n + 20, vii());
for (ll i = 0; i < m; i++) {
ll a, b, t;
cin >> a >> b >> t;
adj[b].push_back({a, t});
}
memset(dp, -1, sizeof dp);
dp[0] = 0;
for (int i = 0; i < n; i++) getToll(i);
for (ll i = 0; i < o; i++) {
ll a, b;
cin >> a >> b;
cout << (dp[b] >= 1e10 ? -1 : dp[b]) << '\n';
}
}
