#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
const int MAXN = 50000 + 10;
const int INF = 1e9 + 10;
int k, n, m, q;
int dp[MAXN];
std::vector<std::pair<int, int>> g[MAXN];
void solve()
{
std::cin >> k >> n >> m >> q;
for(int i = 1 ; i <= m ; ++i)
{
int x, y, z;
std::cin >> x >> y >> z;
x += 1, y += 1;
g[x].push_back({y, z});
}
for(int i = 1 ; i <= q ; ++i)
{
int x, y;
std::cin >> x >> y;
x += 1, y += 1;
if(x > y)
{
std::swap(x, y);
}
for(int i = x ; i <= y ; ++i)
{
dp[i] = INF;
}
dp[x] = 0;
for(int i = x ; i <= y ; ++i)
{
for(auto [to, w] : g[i])
{
dp[to] = std::min(dp[to], dp[i] + w);
}
}
std::cout << (dp[y] != INF ? dp[y] : -1) << "\n";
}
}
void fastIO()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
fastIO();
solve();
return 0;
}
