#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
ll k, n, m, o, dp1[50050], dp2[50050];
vvii adj;
void getToll2(ll u, ll v) {
//cerr << "// getToll(" << u << ", " << v << ")\n";
if (dp2[u] != -1) return;
if (u == v) { dp2[u] = 0; return; }
if (u/k >= v/k) { dp2[u] = 1e10; return; }
//if (u == 1) cerr << "// check1\n";
ll minToll = 1e10;
for (ii edge : adj[u]) {
//if (u == 1) cerr << "// check2 {" << edge.fi << ", " << edge.se << "}\n";
getToll2(edge.fi, v);
if (dp2[edge.fi] >= 1e10) continue;
ll currToll = dp2[edge.fi] + edge.se;
if (currToll < minToll) minToll = currToll;
}
dp2[u] = minToll;
//cerr << "// " << dp2[u] << '\n';
}
void getToll1(ll u) {
//cerr << "// getToll(" << u << ", " << v << ")\n";
if (dp1[u] != -1) return;
//if (u == 1) cerr << "// check1\n";
ll minToll = 1e10;
for (ii edge : adj[u]) {
//if (u == 1) cerr << "// check2 {" << edge.fi << ", " << edge.se << "}\n";
getToll1(edge.fi);
ll currToll = dp1[edge.fi] + edge.se;
if (currToll < minToll) minToll = currToll;
}
dp1[u] = minToll;
//cerr << "// " << dp1[u] << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n >> m >> o;
adj.assign(n + 20, vii());
for (ll i = 0; i < m; i++) {
ll a, b, t;
cin >> a >> b >> t;
adj[b].push_back({a, t});
}
memset(dp1, -1, sizeof dp1);
dp1[0] = 0;
for (int i = 0; i < n; i++) getToll1(i);
for (ll i = 0; i < o; i++) {
memset(dp2, -1, sizeof dp2);
ll a, b;
cin >> a >> b;
if (a == 0) {
cout << (dp1[b] >= 1e10 ? -1 : dp1[b]) << '\n';
} else {
getToll2(a, b);
cout << (dp2[b] >= 1e10 ? -1 : dp2[b]) << '\n';
}
}
}
