/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define all(v) v.begin(),v.end()
#define gen(arr,n,nxt) generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);
#define EPS 0.00000001
const int mo=1e9+7,INF=1e9;
int nxt(){int x;cin>>x;return x;}
vector<pair<int,int> >adj[50001];
int n,k;
inline void dijkstra(int s, vector<int> & d) {
d.assign(n, INF);
d[s] = 0;
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, s});
while (!q.empty()) {
int v = q.top().second;
int d_v = q.top().first;
q.pop();
if (d_v != d[v])
continue;
for (auto edge : adj[v]) {
int to = edge.first;
int len = edge.second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
q.push({d[to], to});
}
}
}
}
inline int dijkstra2(int s,int to) {
vector<int>d;
d.assign(n, INF);
d[s] = 0;
using pii = pair<pair<int, int>,int>;
int a5rak = ((to/k)+1) - (s/k);
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({{0, s},0});
while (!q.empty()) {
int v = q.top().first.second;
int d_v = q.top().first.first;
int limit = q.top().second;
q.pop();
if (d_v != d[v])
continue;
if(v == to)
return d_v;
if(limit >= a5rak)
continue;
for (auto edge : adj[v]) {
int to = edge.first;
int len = edge.second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
q.push({{d[to], to},limit+1});
}
}
}
return INF;
}
signed main(){
Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
//freopen("in.txt","r",stdin);
k=nxt();
n=nxt();
int m=nxt(),qu=nxt();
for(int i=0;i<m;i++){
int x = nxt(),y=nxt(),c= nxt();
adj[x].push_back({y,c});
}
unordered_set<int>from;
int finalAns[qu];
vector<pair<int,int> >v;
vector<pair<int,int>>ans[n];
for(int i=0;i<qu;i++){
v.push_back({nxt(),nxt()});
finalAns[i] = -2;
if(v.back().first == v.back().second)
finalAns[i] = 0;
else if(v.back().first/k >= v.back().second/k)
finalAns[i] = -1;
else
ans[v.back().first].push_back({v.back().second,i});
from.insert(v.back().first);
}
/*for(auto x:from){
if(ans[x].size() <= 100)continue;
vector<int>d;
dijkstra(x,d);
for(auto y:ans[x])
finalAns[y.second] = (d[y.first] == INF?-1:d[y.first]);
}*/
for(int i=0;i<qu;i++){
if(finalAns[i] == -2){
int zh2t = dijkstra2(v[i].first,v[i].second);
cout<<(zh2t == INF?-1:zh2t)<<endl;
}
else cout<<finalAns[i]<<endl;
}
return 0;
}
