#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int k,n,m,o; cin >> k >> n >> m >> o;
vector<vector<pair<int,int>>> neigh(n+k);
vector<vector<pair<int,int>>> ineigh(n+k);
for (int i = 0; i < m; i++)
{
int a,b,t; cin >> a >> b >> t;
neigh[a].push_back({b,t});
ineigh[b].push_back({a,t});
}
int sq=sqrt(n);
vector<vector<pair<pair<int,int>,int>>> query(sq+1);
for (int i = 0; i < o; i++)
{
int a,b; cin >> a >> b;
query[a/sq].push_back({{a,b},i});
}
vector<int> ans(o,-1);
for (int i = 0; i < sq; i++)
{
sort(all(query[i]),[](auto a, auto b){
if(a.first.second==b.first.second) return a<b;
return a.first.second<b.first.second;
});
int mx=((i+1)*sq)-1;
mx=((mx+k-1)/k)*k-1;
vector<vector<int>> dist(k,vector<int>(n+k,1e12));
vector<vector<int>> visited(k,vector<int>(n+k,0));
for (int j = mx-k+1; j <= mx; j++)
{
int jk=j-(mx-k+1);
priority_queue<pair<int,pair<int,int>>> pq;
pq.push({0,{j,2}});
dist[jk][j]=0;
while(!pq.empty()){
int x=pq.top().second.first; int tp=pq.top().second.second; pq.pop();
if(visited[jk][x]) continue;
visited[jk][x]=true;
if(tp==0||tp==2){
for (auto u : neigh[x])
{
if(dist[jk][u.first]>dist[jk][x]+u.second){
dist[jk][u.first]=dist[jk][x]+u.second;
pq.push({-dist[jk][u.first],{u.first,0}});
}
}
}
if(tp==1||tp==2){
for (auto u : ineigh[x])
{
if(dist[jk][u.first]>dist[jk][x]+u.second){
dist[jk][u.first]=dist[jk][x]+u.second;
pq.push({-dist[jk][u.first],{u.first,1}});
}
}
}
}
}
vector<int> sdist(n+k,1e12);
vector<bool> svisit(n+k,0);
for (auto u : query[i])
{
int a=u.first.first,b=u.first.second;
if(b<mx-k+1){
queue<int> toc;
priority_queue<pair<int,int>> pq;
pq.push({0,a});
sdist[a]=0;
while(!pq.empty()){
int x=pq.top().second; pq.pop();
if(svisit[x]) continue;
svisit[x]=true;
toc.push(x);
for (auto u : neigh[x])
{
if(u.first>b) continue;
if(sdist[u.first]>sdist[x]+u.second){
sdist[u.first]=sdist[x]+u.second;
pq.push({-sdist[u.first],u.first});
}
}
}
if(sdist[a]==1e12) sdist[a]=-1;
ans[u.second]=sdist[a];
while(!toc.empty()){
int u=toc.front(); toc.pop();
sdist[u]=1e12;
svisit[u]=false;
}
}else{
int mn=1e12;
for (int j = mx-k+1; j <= mx; j++)
{
mn=min(mn,dist[j-(mx-k+1)][a]+dist[j-(mx-k+1)][b]);
}
if(mn>=1e12){
mn=-1;
}
ans[u.second]=mn;
}
}
}
for (int j = 0; j < o; j++) cout << ans[j] << "\n";
return 0;
}
