#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;
int sq=sqrt(n);
vector<vector<pair<int,int>>> neigh(n+k*2+sq);
vector<vector<pair<int,int>>> ineigh(n+k*2+sq);
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});
}
vector<vector<pair<pair<int,int>,int>>> query(sq+2);
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+1; i++)
{
int mx=((i+1)*sq)-1;
mx=((mx+k)/k)*k-1;
vector<vector<int>> dist(k,vector<int>(n+k*2+sq,1e12));
vector<vector<int>> visited(k,vector<int>(n+k*2+sq,0));
for (int j = mx-k+1; j <= mx; j++)
{
int jk=j-(mx-k+1);
dist[jk][j]=0;
int l=mx-k+1;
while(l<n){
for (int jl = l; jl < l+k; jl++){
for (auto u : neigh[jl])
{
dist[jk][u.first]=min(dist[jk][u.first], dist[jk][jl]+u.second);
}
}
l+=k;
}
l=mx-k+1;
while(l>=0){
for (int jl = l; jl < l+k; jl++){
for (auto u : ineigh[jl])
{
dist[jk][u.first]=min(dist[jk][u.first], dist[jk][jl]+u.second);
}
}
l-=k;
}
}
vector<int> sdist(n+k*2+sq,1e12);
vector<bool> svisit(n+k*2+sq,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[b]>=1e12) ans[u.second]=-1;
else ans[u.second]=sdist[b];
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;
}
