#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int infy = 1e9 + 5;
vector<int> solve(int k, int n, int m, int q, const vector<vector<int> > &g, const vector<pair<int, int> > &v) // riesenie O(q*n^2)
{
vector<int> ans(q);
for (int i = 0; i < q; i++)
{
int a = v[i].first, b = v[i].second;
set<pair<int, int> > pq;
vector<int> dist(n, infy);
pq.insert({0, a});
while (!pq.empty())
{
int d = pq.begin()->first, u = pq.begin()->second;
pq.erase(pq.begin());
if (dist[u] != infy) continue;
dist[u] = d;
for (int j = 0; j < k; j++)
{
int v = (u/k+1)*k + j;
if (g[u][j] == infy || dist[v] != infy) continue;
pq.insert({d+g[u][j], v});
}
}
ans[i] = dist[b] == infy ? -1 : dist[b];
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
while (t--)
{
int k, n, m, q;
cin >> k >> n >> m >> q;
vector<vector<int> > g(n, vector<int> (k, infy));
for (int i = 0, a, b, d; i < m; i++)
{
cin >> a >> b >> d;
g[a][b%k] = d;
}
vector<pair<int, int> > v(q);
for (int i = 0; i < q; i++) cin >> v[i].first >> v[i].second;
vector<int> ans = solve(k, n, m, q, g, v);
for (int i : ans) cout << i << "\n";
}
}
