#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; }