#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<vector<pair<ll,ll>>> vec;
vector<vector<ll>> dis;
vector<bool> vis;
ll raiz;
void bfs(int nodo)
{
priority_queue<pair<ll,ll>> cola;
cola.push({0,nodo});
dis[nodo][nodo]=0;
raiz=nodo;
while(!cola.empty())
{
nodo=cola.top().second;
cola.pop();
if(!vis[nodo]){
for(pair<ll,ll> next:vec[nodo]) {
if(dis[raiz][nodo]+next.second<dis[raiz][next.first]){
dis[raiz][next.first]=dis[raiz][nodo]+next.second;
cola.push({-dis[raiz][next.first],next.first});
}
}
vis[nodo]=true;
}
}
}
void solve()
{
ll k,n,m,o; cin>>k>>n>>m>>o;
vec.assign(n,vector<pair<ll,ll>> ());
vis.assign(n,false);
dis.assign(n,vector<ll> (n,1e9+1));
ll a,b,t,p,g;
while(m--)
{
cin>>a>>b>>t;
if(k==1){
if(b==a+1) vec[a].push_back({b,t});}
else if(a==0){
if(b/k==1) vec[a].push_back({b,t});}
else if(b/k==(a/k)+1) vec[a].push_back({b,t});
}
for(int i=0;i<n;i++){
vis.assign(n,false);
bfs(i);
}
while(o--){
cin>>p>>g;
if(dis[p][g]==1e9+1) cout<<"-1 "<<endl;
else cout<<dis[p][g]<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
}
