#include <bits/stdc++.h>
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define pi pair<int,int>
#define ple tuple<int,int,int>
#define fi first
#define se second
#define ii make_pair
#define isz(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define int long long
using namespace std;
const int N = 5e4 + 10;
const int lg = 17;
const int inf = 1e18;
int n, q, k, m, lim;
bool have[N][lg+2];
vector<int> adj[N];
int res[5][5], tmp[5][5], dp[N][lg+2][5][5];
void minimize (int &a, int b) {
a = min(a, b);
}
int bit (int i, int a) {
return (a >> i) & 1;
}
void Merge (int h[5][5], int g[5][5], int f[5][5]) {
for(int x = 0; x < k; ++x) {
for(int y = 0; y < k; ++y) {
for (int z = 0; z < k; ++z) {
minimize(h[x][z], g[x][y] + f[y][z]);
}
}
}
}
void reset(int x[5][5]) {
for(int i=0; i<k;++i) {
for(int j=0;j<k;++j) {
x[i][j]=inf;
}
}
}
void recur() {
for(int i=0;i<k;++i) {
for(int j=0;j<k;++j) {
res[i][j]=tmp[i][j];
}
}
}
int solve (int u, int v) {
int st = u / k;
int ed = v / k;
int cur = st;
for (int i = lg; i >= 0; --i) {
if (cur + (1 << i) <= ed) {
reset(tmp);
Merge(tmp, res, dp[cur][i]);
recur();
cur += (1 << i);
}
}
int ans = res[u%k][v%k];
if (ans == inf) ans=-1;
return ans;
}
main () {
file("toll");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> k >> n >> m >> q;
FOR(i,0,n) {
FOR(j,0,lg) {
FOR(x,0,k) {
FOR(y,0,k) {
dp[i][j][x][y] = inf;
}
}
}
}
FOR(i,1,m) {
int u,v,w; cin >> u >> v >> w;
dp[u/k][0][u%k][v%k] = w;
}
lim = n / k + 1;
for (int j = 1; j <= lg; ++j) {
for (int i = 0; i + (1 << j) - 1 <= lim; ++i) {
Merge(dp[i][j], dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
}
while(q--) {
int s, t; cin >> s >> t;
reset(res);
for (int i = 0; i < k; ++i) res[i][i] = 0;
cout << solve(s, t) << '\n';
}
}
/// code by yourlove
