#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
vector<pair<int, int>> con[MAXN]; // ind, w
int res[MAXN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int k, n, m, q;
cin >> k >> n >> m >> q;
int a, b, t;
for (int i = 0; i < m; i++)
cin >> a >> b >> t, con[a].push_back({b, t});
fill(res, res + MAXN, INT_MAX);
priority_queue<pair<int, int>> qu;
qu.push({0, 0});
while (!qu.empty())
{
int curr = qu.top().second, w = -(qu.top().first);
cout << curr << " " << w << '\n';
qu.pop();
for (auto i : con[curr])
if (w + i.second < res[i.first])
res[i.first] = w + i.second, qu.push({-res[i.first], i.first});
}
while (q--)
{
cin >> a >> b;
cout << (res[b] == INT_MAX ? -1 : res[b]) << '\n';
}
return 0;
}
