#include <iostream>
#include <vector>
#include <algorithm>
#define int int64_t
using namespace std;
int k;
struct block
{
vector<vector<int>> bl;
block() : bl(vector<vector<int>>(k, vector<int>(k, 1e11))) {}
static block nt()
{
block b;
for (int i = 0; i < k; i++) b.bl[i][i] = 0;
return b;
}
static block merge(const block& b1, const block& b2)
{
block res;
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++)
{
for (int l = 0; l < k; l++)
{
res.bl[i][j] = min(res.bl[i][j], b1.bl[i][l] + b2.bl[l][j]);
}
}
}
return res;
}
void print()
{
return;
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++)
{
cout << bl[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
}
};
struct segtree
{
vector<block> table;
block query(int ql, int qr, int l, int r, int pos)
{
if (ql <= l && r <= qr) return table[pos];
if (qr < l || r < ql) return block::nt();
return block::merge(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
}
void build(const vector<block>& vals, int l, int r, int pos)
{
if (l == r)
{
table[pos] = vals[l];
return;
}
build(vals, l, (l + r)/2, 2*pos + 1);
build(vals, (l + r)/2 + 1, r, 2*pos + 2);
table[pos] = block::merge(table[2*pos + 1], table[2*pos + 2]);
}
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, o;
cin >> k >> n >> m >> o;
n += k - (k % n);
int nbl = (n / k);
vector<block> bls(nbl);
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
int cb = a / k;
a %= k;
b %= k;
bls[cb].bl[a][b] = min(bls[cb].bl[a][b], w);
}
segtree st;
st.table.resize(4*nbl);
st.build(bls, 0, nbl - 1, 0);
for (auto bl : bls)
{
bl.print();
}
for (int i = 0; i < o; i++)
{
int fr, to;
cin >> fr >> to;
if ((fr / k) == (to / k))
{
cout << "-1\n";
continue;
}
auto bl = st.query((fr / k), (to / k) - 1, 0, nbl - 1, 0);
bl.print();
int v = bl.bl[fr % k][to % k];
cout << (v >= 1e11 ? -1 : v) << "\n";
}
}
