#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll inf = 1e18;
struct dsu0 {
vector<int> par, siz;
int n;
int cc;
int largest;
void init(int n) {
assert(n>0);
this->n=n;
cc=n;
par.resize(n+10);siz.resize(n+10);
for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
largest=1;
}
int parent(int x) {
assert(x>=0 && x<n);
return par[x]==x?x:par[x]=parent(par[x]);
}
bool join(int x, int y) {
x=parent(x);y=parent(y);
if (x==y) return false;
cc--;
if (siz[x]<siz[y]) swap(x,y);
siz[x]+=siz[y];par[y]=x;
largest=max(largest,siz[x]);
return true;
}
};
const int maxn = 5e4+10;
int k,n,m,o;
vector<pair<ll,int>> g[maxn];
ll dp[maxn];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>k>>n>>m>>o;
for (int i=0; i<m; i++) {
int u,v; cin>>u>>v;
int w; cin>>w;
g[u].push_back({w,v});
}
for (int i=0; i<n; i++) {
dp[i] = inf;
}
dp[0] = 0;
for (int i=0; i<n; i++) {
if (dp[i]>inf/2) continue;
for (auto ed: g[i]) {
int to = ed.second;
dp[to] = min(dp[to], dp[i]+ed.first);
}
}
while (o--) {
int u,v;
cin>>u>>v;
assert(u==0); //subtask 2
cout<<(dp[v]>inf/2 ? -1 : dp[v])<<"\n";
}
return 0;
}
