#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int maxn = 5e4 + 10, inf = 1e9 + 7, maxsq = 400, maxlg = 21;
//const int mood2 = 97277821, mood3 = 34098487, base = 31;
vector<pair<int, int> > adj[maxn], q[maxn];
vector<int> vec;
int dp[maxn], id[maxn], res[maxn];
int k, n, m, o;
int main()
{
cin >> k >> n >> m >> o;
for(int i = 0; i < m; i++)
{
int v, u, w;
cin >> v >> u >> w;
adj[v].pb(mp(u, w));
}
for(int i = 0; i < o; i++)
{
int v, u;
cin >> v >> u;
q[u].pb(mp(v, i));
vec.pb(u);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for(int i = 0; i < vec.size(); i++)
id[vec[i]] = i;
for(auto x : vec)
{
fill(dp, dp+n, inf);
int xx = id[x];
dp[x] = 0;
for(int i = x-1; i >= 0; i--)
{
for(auto e : adj[i])
{
int u = e.fi, w = e.se;
if(dp[u] >= inf)
continue;
dp[i] = min(dp[i], dp[u] + w);
}
}
for(auto y : q[x])
res[y.se] = dp[y.fi];
}
for(int i = 0; i < o; i++)
{
if(res[i] >= inf)
cout << -1 << '\n';
else
cout << res[i] << '\n';
}
}
