#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define debug(x) cout << #x << "= " << x << ", "
#define ll long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define SZ(x) (int) x.size()
#define wall cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e4 + 10 , maxl = 17 , maxk = 7 , inf = 1e9;
int n, m , q , k , dis[maxn][maxl][maxk];
vector <pair<int , int>> adj[maxn];
int find_nex(int v , int jmp , int ps)
{
int now = v / k;
int to = now + (1 << jmp);
to *= k;
to += ps;
return min(to , n);
}
int Find_ans(int nb , int np , int fb , int fp)
{
int res[2][maxk];
for(int i = 0 ; i < k ; i++) res[0][i] = res[1][i] = inf;
res[0][np] = 0;
int l = nb * k , fbi = (fb - nb) , upd = 0 , val = fb - nb;
for(int jmp = 0 ; jmp < maxl ; jmp++) if((val >> jmp) & 1)
{
for(int i = 0 ; i < k ; i++) res[upd ^ 1][i] = inf;
for(int from = 0 ; from < k ; from++)
{
int v = l + from;
for(int to = 0 ; to < k ; to++)
{
res[upd ^ 1][to] = min(res[upd ^ 1][to] , res[upd][from] + dis[v][jmp][to]);
}
}
nb += (1 << jmp);
l = nb * k;
upd ^= 1;
}
return (res[upd][fp] == inf ? -1 : res[upd][fp]);
}
int32_t main()
{
fast;
cin >> k >> n >> m >> q;
for(int i = 0 ; i < maxn ; i++)
for(int j = 0 ; j < maxl ; j++)
for(int k = 0 ; k < maxk ; k++)
dis[i][j][k] = inf;
for(int i = 0 ; i < m ; i++)
{
int v , u , c; cin >> v >> u >> c;
adj[v].pb({u , c});
dis[v][0][(u % k)] = c;
}
for(int jmp = 1 ; jmp < maxl ; jmp++)
for(int v = 0 ; v < n ; v++)
for(int from = 0 ; from < k ; from++)
for(int to = 0 ; to < k ; to++)
dis[v][jmp][to] = min(dis[v][jmp][to] , dis[v][jmp - 1][from] + dis[find_nex(v , jmp - 1 , from)][jmp - 1][to]);
while(q--)
{
int v , u; cin >> v >> u;
if(v / k >= u / k)
{
cout << -1 << '\n';
continue;
}
cout << Find_ans(v / k , v % k , u / k , u % k) << '\n';
}
return 0;
}
