#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 , maxsq = 100 , maxk = 7 , inf = 1e9;
int n , m , q , k , dis[maxn] , dis_jmp[maxn][maxk];
vector <pair<int , int>> adj[maxn];
vector <int> vec;
void Relax()
{
for(auto u : vec) dis[u] = inf;
vec.clear();
}
void find_nex(int now , int to)
{
int l = now * k , r = min(n , l + k);
for(int i = l ; i < r ; i++) vec.pb(i);
if(now == to) return;
for(int i = l ; i < r ; i++)
for(auto u : adj[i])
dis[u.F] = min(dis[u.F] , dis[i] + u.S);
find_nex(now + 1 , to);
}
void Build(int num)
{
int l = num * k , r = min(n , l + k);
int l2 = (num + maxsq) * k;
for(int i = l ; i < r ; i++)
{
dis[i] = 0;
find_nex(num , num + maxsq);
for(int j = 0 ; j < k ; j++)
dis_jmp[i][j] = dis[l2 + j];
Relax();
}
}
void jmp_nex(int a , int b)
{
int l = a * k , r = min(n , l + k) , l2 = (a + maxsq) * k;
for(int i = l ; i < r ; i++) vec.pb(i);
if(a == b) return;
for(int i = l ; i < r ; i++)
for(int j = 0 ; j < k ; j++)
dis[l2 + j] = min(dis[l2 + j] , dis[i] + dis_jmp[i][j]);
jmp_nex(a + maxsq , b);
}
void Find_dis(int a , int b)
{
int tmp = (a + maxsq) / maxsq;
tmp *= maxsq;
if(b <= tmp)
{
find_nex(a , b);
return;
}
find_nex(a , tmp);
int tmp2 = b / maxsq;
tmp2 *= maxsq;
jmp_nex(tmp , tmp2);
find_nex(tmp2 , b);
}
int32_t main()
{
fast;
cin >> k >> n >> m >> q;
for(int i = 0 ; i < n ; i++) dis[i] = inf;
for(int i = 0 ; i < m ; i++)
{
int v , u , c; cin >> v >> u >> c;
adj[v].pb({u , c});
}
for(int i = 0 ; (i + maxsq) * k < n ; i += maxsq) Build(i);
while(q--)
{
int v , u; cin >> v >> u;
if(v > u)
{
cout << -1 << '\n';
continue;
}
dis[v] = 0;
vec.pb(v);
Find_dis(v / k , u / k);
cout << (dis[u] == inf ? -1 : dis[u]) << '\n';
Relax();
}
return 0;
}
