#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];
map<int,ll> dp[maxn];
ll f(int u, int v) {
if (u==v) return 0;
if (dp[u].count(v)) return dp[u][v];
ll res = inf;
for (auto ed: g[u]) {
res = min(res, ed.first+f(ed.second,v));
}
return dp[u][v] = res;
}
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});
}
while (o--) {
int u,v;
cin>>u>>v;
ll res = f(u,v);
if (res>inf/2) res=-1;
cout<<res<<"\n";
}
return 0;
}
