#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define fi first
#define se second
#define left __left
#define right __right
#define prev __prev
#define next __next
template <class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
else return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) return x = y, true;
else return false;
}
const long long INF = (long long) 1e18 + 7;
#define MAX_NODE 50500
#define MAX_QUERY 10100
int K, numNode, numEdge, numQuery;
vector<pair<int, int>> adj[MAX_NODE + 2];
ll dist[MAX_NODE + 2];
void Dijkstra(int s) {
#define ii pair<long long, int>
FOR(i, 1, numNode) dist[i] = INF;
priority_queue<ii, vector<ii>, greater<ii>> q;
#define PUSH(s) q.push(make_pair(dist[(s)], (s)))
dist[s] = 0;
PUSH(s);
while (!q.empty()) {
ll d = q.top().fi;
int u = q.top().se;
q.pop();
if (d != dist[u]) continue;
for (const pair<int, int> &e : adj[u]) {
int v = e.fi, w = e.se;
if (minimize(dist[v], dist[u] + w)) PUSH(v);
}
}
FOR(i, 1, numNode) if (dist[i] == INF) dist[i] = -1;
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
cin >> K >> numNode >> numEdge >> numQuery;
FOR(i, 1, numEdge) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
}
Dijkstra(0);
while (numQuery--) {
int u, v;
cin >> u >> v;
assert(u == 0);
cout << dist[v] << "\n";
}
return 0;
}
