#include <bits/stdc++.h>
using namespace std;
int inf = 1e9;
int k,n,m,q,t;
vector<pair<int,int>>g[50005],gr[50005];
int ans[10005];
int dist[50005];
struct ura
{
int x,y,idx;
};
void dijkstral(int start,int leftbound)
{
priority_queue<pair<int,int>>pq;
pq.push({0,start});
while (!pq.empty())
{
int timp = -pq.top().first,nod = pq.top().second;
pq.pop();
if (dist[nod] == inf)
{
dist[nod] = timp;
for (auto vecin : gr[nod])
{
if (vecin.first >= leftbound)
pq.push({-(vecin.second + timp),vecin.first});
}
}
}
}
void dijkstrar(int start,int rightbound)
{
priority_queue<pair<int,int>>pq;
pq.push({0,start});
while (!pq.empty())
{
int timp = -pq.top().first,nod = pq.top().second;
pq.pop();
if (dist[nod] == inf)
{
dist[nod] = timp;
for (auto vecin : g[nod])
{
if (vecin.first <= rightbound)
pq.push({-(vecin.second + timp),vecin.first});
}
}
}
}
void solve(int l,int r,vector<ura>&v)
{
if (l == r)
return;
int mij = (l + r) / 2;
///pentru query-uri cu st <= mij si dr > mij, sigur trec prin ceva din mij
///incerc fiecare din cele k valori ale mij ca fiind "punctul de trecere"
///valorile de mijloc sunt mij * k, mij * k + 1,...mij * k + k - 1
vector<ura>v1,v2,s;
for (auto it : v)
{
if (it.y / k <= mij)
v1.push_back(it);
else if (it.x / k > mij)
v2.push_back(it);
else
s.push_back(it);
}
if (v1.size() != 0)
solve(l,mij,v1);
if (v2.size() != 0)
solve(mij + 1,r,v2);
for (int i = mij * k; i < min((mij + 1) * k,n + 1); i++)
{
///i este nodul de trecere
///fac un dijkstra in stanga si unul in dreapta din nodul i, bounded by [l * k, r * (k + 1) - 1] si incerc sa rezolv fiecare query din s
for (int j = l * k; j < min(n + 1,(r + 1) * k); j++)
dist[j] = inf;
dijkstral(i,l * k);
dist[i] = inf;
dijkstrar(i,(r + 1) * k - 1);
for (auto it : s)
{
ans[it.idx] = min(ans[it.idx],dist[it.x] + dist[it.y]);
//cout << "Q " << dist[it.x] << ' ' << dist[it.y] << '\n';
}
for (int j = l * k; j < min(n + 1,(r + 1) * k); j++)
dist[j] = inf;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k >> n >> m >> q;
t = (n - 1) / k;
for (int i = 1; i <= m; i++)
{
int x,y,z;
cin >> x >> y >> z;
g[x].push_back({y,z});
gr[y].push_back({x,z});
}
vector<ura>v;
for (int i = 1; i <= q; i++)
{
ura aux;
cin >> aux.x >> aux.y;
aux.idx = i;
v.push_back(aux);
}
for (int i = 1; i <= q; i++)
ans[i] = inf;
solve(0,t,v);
for (int i = 1; i <= q; i++)
{
if (ans[i] == inf)
cout << -1 << '\n';
else
cout << ans[i] << '\n';
}
return 0;
}
