// 57?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int MM = 5e4+5;
int n,o,k,m; ll dp[MM]; vector<pi> adj[MM];
int dfs(int u, int b){
if(dp[u] != -1) return dp[u];
if(u == b){
dp[u] = 0;
return 0;
}
dp[u] = 1e9;
for(auto [v,w] : adj[u]){
dfs(v,b);
dp[u] =min(dp[u],dp[v]+w);
}
return dp[u];
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> k >> n >> m >> o;
for(int i = 0; i < m; i++){
int a,b,t; cin >> a >> b >> t;
adj[a].emplace_back(b,t);
}
while(o--){
int a,b; cin >> a >> b;
memset(dp,-1,sizeof dp);
dfs(a,b);
cout << (dp[a]>=1e9 ? -1 : dp[a]) << "\n";
}
}
