#include <bits/stdc++.h>
using namespace std;
#define pb push_back
//#define int long long
const int maxN = 4e5 + 7;
vector<pair<int, int>> g[maxN];
int dp[maxN];
void solve() {
int k, n, m, o;
cin >> k >> n >> m >> o;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].pb({v, w});
}
while(o--) {
int a, b;
cin >> a >> b;
for(int i = 0; i < n; i++) dp[i] = 1e9;
queue<int> q;
q.push(a);
dp[a] = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
for(auto [u, w] : g[v]) {
if(dp[u] > dp[v] + w) {
dp[u] = dp[v] + w;
q.push(u);
}
}
}
if(dp[b] == 1e9) cout << -1 << '\n';
else cout << dp[b] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("input.txt", "r", stdin);
int t = 1;
//cin >> t;
while(t--) solve();
}
