#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const ll mod = 1e9 + 7;
const ll INF = 1e18;
//--------------------------------------------------------------------
const ll BLOCK = 250;
const ll N = 50003;
ll n, k, m ,o;
vector<pa> g[N];
ll dp[N * 10];
ll dist[BLOCK + 5][6][6];
void calc(ll block, ll x, ll y, ll stt) {
if(x > n) return;
fill(dp + x, dp + y + 1, INF);
dp[x] = 0;
ll id = 0;
FOR(u, x, y) {
if(dp[u] != INF)
for(auto e : g[u]) {
ll v = e.fi, w = e.se;
dp[v] = min(dp[v], dp[u] + w);
}
if(u >= y - k + 1) {
id++;
dist[block][stt][id] = dp[u];
}
}
assert(id == k);
}
ll calc2(ll u, ll v) { // tinh luon ans tu u den v vi u v cung block
fill(dp + u, dp + v + 1, INF);
dp[u] = 0;
FOR(i, u, v) {
if(dp[i] != INF) {
for(auto e : g[i]) {
ll j = e.fi, w = e.se;
dp[j] = min(dp[j], dp[i] + w);
}
}
}
if(dp[v] < INF) return dp[v];
return -1;
}
ll c[6], c_new[6];
ll cnt[N], d[N];
void calc3(ll x, ll block) { // day u ve k con cuoi cung trong blockl
ll y = (block + 1) * BLOCK * k - 1;
if(y - x + 1 <= k) {
FOR(i, 1, 5) c[i] = INF;
c[d[x]] = 0;
return;
}
fill(dp + x, dp + y + 1, INF);
dp[x] = 0;
ll id = 0;
FOR(u, x, y) {
if(dp[u] != INF)
for(auto e : g[u]) {
ll v = e.fi, w = e.se;
dp[v] = min(dp[v], dp[u] + w);
}
if(u >= y - k + 1) {
id++;
c[id] = dp[u];
}
}
}
ll calc4(ll x, ll y) { // day 5 con cuoi cung cua blockr - 1 ve r
fill(dp + x, dp + y + 1, INF);
FOR(i, 1, k) {
dp[x + i - 1] = c[i];
}
FOR(i, x, y) {
if(dp[i] != INF) {
for(auto e : g[i]) {
ll j = e.fi, w = e.se;
dp[j] = min(dp[j], dp[i] + w);
}
}
}
if(dp[y] < INF) return dp[y];
return -1;
}
ll solve(ll u, ll v) {
ll tangu = u / k, tangv = v / k;
ll blockl = tangu / BLOCK;
ll blockr = tangv / BLOCK;
if(blockl == blockr) return calc2(u, v);
calc3(u, blockl);
FOR(block, blockl + 1, blockr - 1) {
ll xpre = block * BLOCK * k - k;
FOR(i, 1, k) c_new[i] = INF;
FOR(i, 1, k) {
for(auto e : g[xpre]) {
ll y = e.fi, w = e.se;
c_new[d[y]] = min(c_new[d[y]], c[i] + w);
}
xpre++;
}
FOR(j, 1, k) {
c[j] = INF;
FOR(i, 1, k) {
if(dist[block][i][j] > INF) continue;
c[j] = min(c[j], c_new[i] + dist[block][i][j]);
}
}
}
return calc4(blockr * BLOCK * k - k, v);
}
void hbmt() {
cin >> k >> n >> m >> o;
FOR(i, 0, n - 1) {
d[i] = ++cnt[i / k];
}
FOR(i, 1, m) {
ll u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
memset(dist, 0x3f, sizeof dist);
for(int i = 0; i * BLOCK * k <= n; i++) {
ll x = i * BLOCK * k; // so dau tien cua tang
ll y = (i + 1) * BLOCK * k - 1; // so cuoi cung cua tang
FOR(j, 1, k) {
calc(i, x, y, j);
x++;
}
}
FOR(i, 1, o) {
ll u, v ;
cin >> u >> v;
ll tangu = u / k, tangv = v / k;
cout << solve(u, v) << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#define NAME "hbmt"
if(fopen(NAME".inp", "r")) {
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
//int t;cin>>t;while(t--)
hbmt();
return 0;
}
