#include <bits/stdc++.h>
using namespace std;
vector < pair <int , int> > adiacenta[50005][2] , intrebari[50005];
int rezultat[10001] , distanta[50005];
void Divide (const int stanga , const int dreapta , const int factor)
{
if (stanga >= dreapta)
{ return; }
const int inceput = stanga + (dreapta - stanga + 1) / factor / 2 * factor;
const int sfarsit = stanga + ((dreapta - stanga + 1) / factor / 2 + 1) * factor - 1;
Divide(stanga , inceput - 1 , factor);
Divide(sfarsit + 1 , dreapta , factor);
vector < pair < int , pair <int , int> > > actual;
for (int __nod = stanga ; __nod <= sfarsit ; __nod++) {
for (auto& intrebare : intrebari[__nod]) {
if (intrebare.first >= inceput && intrebare.first <= dreapta)
{ actual.emplace_back(__nod , intrebare); rezultat[intrebare.second] = INT32_MAX; }
}
}
for (int nod = inceput ; nod <= sfarsit ; nod++)
{
for (int __nod = stanga ; __nod <= dreapta ; __nod++)
{ distanta[__nod] = INT32_MAX; }
distanta[nod] = 0;
for (int __nod = nod ; __nod <= dreapta ; __nod++) {
if (distanta[__nod] != INT32_MAX) {
for (auto& vecin : adiacenta[__nod][0])
{ distanta[vecin.first] = min(distanta[vecin.first] , distanta[__nod] + vecin.second); }
}
}
for (int __nod = nod ; __nod >= stanga ; __nod--) {
if (distanta[__nod] != INT32_MAX) {
for (auto& vecin : adiacenta[__nod][1]) {
{ distanta[vecin.first] = min(distanta[vecin.first] , distanta[__nod] + vecin.second); }
}
}
}
for (auto& intrebare : actual) {
if (distanta[intrebare.first] != INT32_MAX && distanta[intrebare.second.first] != INT32_MAX)
{ rezultat[intrebare.second.second] = min(rezultat[intrebare.second.second] , distanta[intrebare.first] + distanta[intrebare.second.first]); }
}
}
for (auto& intrebare : actual) {
if (rezultat[intrebare.second.second] == INT32_MAX)
{ rezultat[intrebare.second.second] = -1; }
}
}
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int factor , numar_noduri , numar_muchii , numar_intrebari;
cin >> factor >> numar_noduri >> numar_muchii >> numar_intrebari;
numar_noduri = ((numar_noduri - 1) / factor + 1) * factor;
while (numar_muchii--)
{
int nod[2] , cost;
cin >> nod[0] >> nod[1] >> cost;
adiacenta[nod[0]][0].emplace_back(nod[1] , cost);
adiacenta[nod[1]][1].emplace_back(nod[0] , cost);
}
for (int indice = 1 ; indice <= numar_intrebari ; indice++)
{
int nod[2]; cin >> nod[0] >> nod[1];
intrebari[nod[0]].emplace_back(nod[1] , indice);
}
Divide(0 , numar_noduri - 1 , factor);
for (int indice = 1 ; indice <= numar_intrebari ; indice++)
{ cout << rezultat[indice] << '\n'; }
return 0;
}
