#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e18;
const int MAXN = 5e4+100;
int K, N, M, Q;
vector<pii> g[MAXN];
vector<int> toposort;
bool vis[MAXN];
void dfs(int v){
vis[v] = true;
for(auto [u, w] : g[v]){
if(!vis[u])
dfs(u);
}
toposort.pb(v);
}
void solve(){
cin >> K >> N >> M >> Q;
rep(m, 0, M){
int a, b, t;
cin >> a >> b >> t;
g[a].pb({b, t});
}
rep(i, 0, N){
if(!vis[i])
dfs(i);
}
reverse(all(toposort));
vector<ll> dp0(N, INF);
dp0[0] = 0;
for(int v : toposort){
for(auto [u, w] : g[v]){
dp0[u] = min(dp0[u], dp0[v] + w);
}
}
vector<ll> k1(N, INF);
vector<int> comp(N, -1);
int szcomp = 0;
for(int v : toposort){
if(comp[v] == -1){
comp[v] = szcomp++;
k1[v] = 0;
}
for(auto [u, w] : g[v]){
comp[u] = comp[v];
k1[u] = k1[v] + w;
}
}
rep(q, 0, Q){
int a, b;
cin >> a >> b;
if(K == 1){
if(comp[a] == comp[b] && k1[a] <= k1[b])
cout << k1[b] - k1[a] << "\n";
else
cout << "-1\n";
continue;
}
if(a == 0){
if(dp0[b] == INF)
cout << "-1\n";
else
cout << dp0[b] << "\n";
} else{
vector<ll> dp(N, INF);
dp[a] = 0;
for(int v : toposort){
if(v == b) break;
for(auto [u, w] : g[v]){
dp[u] = min(dp[u], dp[v] + w);
}
}
if(dp[b] == INF)
cout << "-1\n";
else
cout << dp[b] << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(nullptr);
solve();
return 0;
}
