#include <bits/stdc++.h> using namespace std; #define int long long int k, n, e, o; vector<vector<pair<int, int>>> g; vector<vector<pair<int, int>>> rg; vector<vector<pair<int, int>>> m; vector<int> ns; vector<vector<int>> dpl; vector<vector<int>> dpr; void dnc(int l, int r){ if(l > r) return; for(int y = 0; y < k; y++){ for(int z = l*k; z < min((r+1)*k, n); z++){ dpl[y][z] = 2e9; dpr[y][z] = 2e9; } } int mid = (l+r)/2; int h = 0; for(int y = mid*k; y < min((mid+1)*k, n); y++){ dpl[h][y] = 0; dpr[h][y] = 0; h++; } h = 0; for(int y = mid*k; y < min((mid+1)*k, n); y++){ for(int j = y; j < min(k*(r+1), n); j++){ if(dpr[h][j] == 2e9) continue; for(auto [a, b] : g[j]){ dpr[h][a] = min(dpr[h][a], dpr[h][j]+b); } } for(int j = y; j >= l*k; j--){ if(dpl[h][j] == 2e9) continue; for(auto [a, b] : rg[j]){ dpl[h][a] = min(dpl[h][a], dpl[h][j]+b); } } h++; } for(int i = l*k; i < min((mid+1)*k, n); i++){ while(m[i].size() > 0){ if((m[i].back().first/k) >= mid){ int idx = m[i].back().second; h = 0; for(int y = mid*k; y < min((mid+1)*k, n); y++){ ns[idx] = min(ns[idx], dpl[h][i] + dpr[h][m[i].back().first]); h++; } m[i].pop_back(); }else{ break; } } } dnc(l, mid-1); dnc(mid+1, r); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> k >> n >> e >> o; ns.resize(o, 2e9); g.resize(n); rg.resize(n); for(int i = 0; i < e; i++){ int u, v, t; cin >> u >> v >> t; g[u].push_back({v, t}); rg[v].push_back({u, t}); } m.resize(n); int co = 0; while(o--){ int a, b; cin >> a >> b; m[a].push_back({b, co}); co++; } for(int i = 0; i < n; i++){ sort(m[i].begin(), m[i].end()); } dpl.resize(k, vector<int>(n, 2e9)); dpr.resize(k, vector<int>(n, 2e9)); dnc(0, (n-1)/k); for(int i = 0; i < ns.size(); i++){ if(ns[i] == 2e9){ ns[i] = -1; } cout << ns[i] << "\n"; } return 0; }