#include <bits/stdc++.h>
template <class A, class B>
bool maximize (A &a, const B b){
if (a < b) {
a = b;
return true;
} return false;
}
template <class A, class B>
bool minimize (A &a, const B b) {
if (a > b) {
a = b;
return true;
} return false;
}
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define fi first
#define se second
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define BIT(mask,i) ((mask>>(i))&1)
#define ll long long
using namespace std;
int K, N, M, Q;
vector <pair <int, int>> G[50005];
void init(void) {
cin >> K >> N >> M >> Q;
FOR(i, 1, M) {
int u, v, w; cin >> u >> v >> w;
G[u].push_back({v, w});
}
}
namespace sub1 {
void solve() {
while (Q--) {
int sour, fin;
cin >> sour >> fin;
vector <long long> dist(N + 2, 1e18);
priority_queue <array <long long, 2>, vector <array <long long, 2>>, greater <array <long long, 2>>> pq;
pq.push({dist[sour] = 0, sour});
while (!pq.empty()) {
int u = pq.top()[1];
long long cost = pq.top()[0];
pq.pop();
if (cost > dist[u]) continue;
for (auto it : G[u]) {
int v = it.fi, w = it.se;
if (minimize(dist[v], cost + w)) {
pq.push({dist[v], v});
}
}
}
cout << (dist[fin] >= 1e18 ? - 1 : dist[fin]) << "\n";
}
}
}
void process(void) {
sub1::solve();
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define koa "kieuoanh"
if (fopen(koa".inp", "r")) {
freopen(koa".inp", "r", stdin);
freopen(koa".out", "w", stdout);
}
init();
process();
return 0;
}
