#include <bits/stdc++.h>
#define int long long
using namespace std;
int k,a,b,c;
vector <pair<int,int>> z[1000005];
int cnt[100005];
int bruh=1e18;
void dijkstra(int sta,int fin){
for (int i=sta;i<=fin;i++){
cnt[i]=bruh;
}
priority_queue<pair<int,int> , vector <pair<int,int>> , greater<pair<int,int>> > q;
q.push({0,sta});
cnt[sta]=0;
while (q.size()){
pair<int,int> pos=q.top();
q.pop();
int pos1=pos.second;
int val=pos.first;
if (val>cnt[pos1]){
continue;
}
if (pos1/5>fin/5){
continue;
}
for (auto p:z[pos1]){
if (cnt[p.first]>p.second+val){
cnt[p.first]=p.second+val;
q.push({cnt[p.first],p.first});
}
}
}
if (cnt[fin]!=bruh){
cout << cnt[fin] << "\n";
}else{
cout << -1 << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> k >> a >> b >> c;
for (int i=1;i<=b;i++){
int x,y,t;
cin>> x >> y >> t;
z[x].push_back({y,t});
z[y].push_back({x,t});
}
for (int i=1;i<=c;i++){
int x,y;
cin >> x >> y;
dijkstra(x,y);
}
return 0;
}
