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