#include <bits/stdc++.h>
/*
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
*/
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define F first
#define S second
#define pb push_back
#define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
#define md(a) ((a%mod+mod)%mod)
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc id<<1
#define rc lc|1
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll const maxn=5e4+10, INF=1e9+10, LOG=22, sq=65;
ll poww(ll a, ll b, ll mod) {
if (b == 0) return 1;
return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}
int n, m, k, o, f[maxn], l[maxn], dis[maxn];
vector<pair<pii, int>> E;
map<pii, int> mp;
int solve(int a, int b)
{
if(a==b) return 0;
if(a>b || !f[a] || !l[b]) return -1;
if(mp[{a, b}]!=0) return mp[{a, b}];
fill(dis+a, dis+b+1, INF);
vector<int> s;
dis[a]=0;
for(int i=f[a];i<=min(m, l[b]);i++)
{
auto t=E[i-1];
int v=t.F.F, u=t.F.S, w=t.S;
if(dis[v]+w<dis[u]) dis[u]=dis[v]+w;
// s.pb(u);
}
// for(int i:s) mp[{a, i}]=dis[i];
mp[{a, b}]=dis[b];
return mp[{a, b}];
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>k>>n>>m>>o;
for(int i=1;i<=m;i++)
{
int v, u, w;
cin>>v>>u>>w;
E.pb({{v, u}, w});
}
fill(f, f+maxn, 0);
fill(l, l+maxn, 0);
int cur=1;
sort(all(E));
for(auto t:E)
{
int v=t.F.F, u=t.F.S;
if(f[v]==0) f[v]=cur;
l[u]=cur;
cur++;
}
while(o--)
{
int a, b;
cin>>a>>b;
int ans=solve(a, b);
if(ans<INF) cout<<ans<<"\n";
else cout<<-1<<"\n";
}
return 0;
}
