#include <bits/stdc++.h>
#include <random>
#define int long long
#define ff first
#define ss second
using namespace std;
const int inf = 1e9;
void dfs(vector<int>& dp, vector<map<int,int>>& graph, int cur)
{
for (auto a : graph[cur])
{
dp[a.ff] = min(dp[a.ff],dp[cur]+a.ss);
dfs(dp,graph,a.ff);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k,n,m,o;
cin >> k >> n >> m >> o;
if (k==1)
{
vector<int> edges(n-1,inf);
for (int i = 0; i < m; i++)
{
int a,b,c;
cin >> a >> b >> c;
edges[a] = c;
}
vector<int> pref_sum(n-1,0);
pref_sum[0] = edges[0];
for (int i = 1; i < n-1; i++)
pref_sum[i] = pref_sum[i-1]+edges[i];
auto sum = [&](int l,int r)
{
return pref_sum[r] - (l > 0 ? pref_sum[l-1] : 0LL);
};
for (int i = 0; i < o; i++)
{
int a,b;
cin >> a >> b;
if (sum(a,b-1) >= inf)
cout << -1 << '\n';
else
cout << sum(a,b-1) << '\n';
}
}
else
{
//turk milleti meslin baban!!!!
vector<map<int,int>> graph(n);
for (int i = 0; i < m; i++)
{
int a,b,t;
cin >> a >> b >> t;
graph[a][b] = t;
}
vector<int> dp(n,inf);
dp[0] = 0;
dfs(dp,graph,0);
for (int i = 0; i < o; i++)
{
int a,b;
cin >> a >> b;
if (dp[b] >= inf)
cout << "-1\n";
else
cout << dp[b] << '\n';
}
}
return 0;
}
