#include <iostream>
#include "bits/stdc++.h"
//#include <memory> // For std::unique_ptr
using namespace std;
typedef long long ll;
#define range(i, a, b) for(int (i) = a; (i) < (b); (i)++)
//#define int long long
#define mod 998244353
//#define mod 1000000007
//#define mod 998244853
//#define mod 4294967296
#define infinity 999999999
//#define infinity 99
//#define infinity 999999999999999
//#define infinity LONG_LONG_MAX
#define yes "yes"
#define no "no"
#define No "No"
#define Yes "Yes"
#define YES "YES"
#define NO "NO"
#define all(x) x.begin(), x.end()
// TREE OF 11 edges 11 1 2 1 3 1 4 2 5 3 6 6 9 3 7 7 10 7 11 4 8
void print() {
cout << "\n";
}
void print(const string &s) {
cout << s << '\n';
}
void print(double x) {
cout << x << '\n';
}
void print(int a) {
cout << a << '\n';
}
void print(pair<int, int> p) {
cout << "(" << p.first << ", " << p.second << ")";
}
void print(int A[], int N) {
range(a, 0, N) cout << A[a] << ' ';
cout << '\n';
}
void print(bool A[], int N) {
range(a, 0, N) cout << A[a] << ' ';
cout << '\n';
}
void print(const vector<int> &v, int length) {
for (int x: v) {
cout << x << ' ';
length--;
if (length < 0) break;
}
cout << '\n';
}
void print(const vector<int> &v) {
for (int x: v) cout << x << ' ';
cout << '\n';
}
void print(const vector<string> &v) {
for (const string &x: v) cout << x << '\n';
cout << "\n\n\n";
}
void print(const vector<bool> &v) {
for (bool x: v) cout << x << ' ';
cout << '\n';
}
void print(const vector<vector<int>> &v) {
for (const auto &x: v) {
print(x);
}
}
void print(const vector<pair<int, int>> &v) {
for (auto it: v) {
print(it);
cout << ' ';
}
cout << "\n";
}
void print(const map<int, int> &mp) {
cout << "{";
for (auto it: mp) cout << it.first << ": " << it.second << ", ";
cout << "}\n";
}
void print(pair<int, int> A[], int N) {
range(a, 0, N) {
cout << "(" << A[a].first << ", " << A[a].second << ") ";
}
cout << '\n';
}
void print(const multiset<int> &st) {
for (int i: st) cout << i << ' ';
cout << '\n';
}
void print(const multiset<pair<int, int>> &st) {
for (auto i: st) {
print(i);
cout << ' ';
}
cout << '\n';
}
void print(const set<int> &st) {
for (int i: st) cout << i << ' ';
cout << '\n';
}
void print(const unordered_set<int> &st) {
for (int i: st) cout << i << ' ';
cout << '\n';
}
void print(queue<int> q) {
for (size_t i = 0; i < q.size(); i++) {
cout << q.front() << ' ';
q.push(q.front());
q.pop();
}
print();
}
void print(const map<pair<int, int>, int> &mp) {
cout << "{";
for (auto it: mp) cout << '(' << it.first.first << ", " << it.first.second << ")" << ": " << it.second << ", ";
cout << "}\n";
}
void print(pair<int, pair<int, int>> p) {
cout << "(" << p.first << ", ";
print(p.second);
print(")");
}
long long power(long long x, int y, int p) {
if (y == 0) return 1;
long long res = 1;
x = x % p;
if (x == 0) return 0;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
long long multiply_mod(long long a, long long b) {
long long res = 0;
a %= mod;
while (b) {
if (b & 1)
res = (res + a) % mod;
a = (2 * a) % mod;
b >>= 1;
}
return res;
}
int get_digit_sum(int x) {
int ans = 0;
while (x) {
ans += (1);
x /= 10;
}
return ans;
}
int sher() {
int x;
cin >> x;
return x;
}
string read() {
string s;
cin >> s;
return s;
}
vector<int> read_vector(int len) {
vector<int> temp(len);
range(a, 0, len) cin >> temp[a];
return temp;
}
int inverse(int x, int p) {
return power(x, p - 2, p);
}
int random_int() {
int a = rand(), b = rand(), c = rand();
return a * b + c;
}
int random_between(int l, int r) {
if (r == l) return r;
return (random_int() % (r - l)) + l;
}
int ceil(int a, int b) {
int ans = a / b;
if (a % b != 0) ans++;
return ans;
}
pair<bool, int> my_sqrt(int x) {
int p = (int) sqrt(x);
int ans = -1;
range(i, -5, 5) {
int c = p + i;
if (c < 0) continue;
if (c * c == x) return {true, c};
if (c * c <= x) ans = c;
}
return {false, ans};
}
vector<int> fact;
int binomial(int n, int r) {
if (n < 0 || r < 0) return 0;
if (r > n) return 0;
if (r == n) return 1;
int num = fact[n];
int den = fact[r] * fact[n - r];
den %= mod;
den = inverse(den, mod);
return ((num * den) % mod);
}
void factorials(int MAXN) {
fact.push_back(1);
range(a, 1, MAXN) fact.push_back((fact.back() * a) % mod);
}
vector<int> spf;
void sieve(int MAXN) {
spf.resize(MAXN);
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
spf[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j < MAXN; j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
vector<int> get_divisors(int x) {
if (x == 1) return {1};
int p = spf[x];
auto prev = get_divisors(x / p);
vector<int> ans;
for (int d: prev) {
ans.push_back(d * p);
if (d % p != 0) ans.push_back(d);
}
return ans;
}
int get_mobius(int n) {
int hehe = n;
if (n == 1) return 1;
int ans = 1;
while (n > 1) {
int p = spf[n];
n /= p;
if (n % p == 0) return 0;
ans *= -1;
}
return ans;
}
struct Query {
int first, second, idx;
};
int n, m, k;
vector<int> arr;
vector<pair<int, int>> *adj;
int lefta[50001];
int righta[50001];
bool visited[50001];
int ans[10001];
bool valid(int t, int from = 0, int to = n - 1) {
return t >= min(from, to) && t <= max(from, to);
}
void djikstra(int from, int to, int save[]) {
range(_, from, to + 1) visited[_] = false, save[_] = infinity;
range(_, to, from + 1) visited[_] = false, save[_] = infinity;
save[from] = 0;
priority_queue<pair<int, int>> pq;
pq.emplace(0, from);
while (!pq.empty()) {
auto it = pq.top();
pq.pop();
int d = -it.first, curr = it.second;
visited[curr] = true;
for (auto nb: adj[curr]) {
if (!valid(nb.first, from, to)) continue;
if ((to > from) != (nb.first > curr)) continue;
if (visited[nb.first]) continue;
int new_dist = save[curr] + nb.second;
if (new_dist < save[nb.first]) {
save[nb.first] = new_dist;
pq.emplace(-new_dist, nb.first);
}
}
}
}
void dac(int l, int r, vector<Query> queries) {
if (l == r) return;
int mid = (l + r) / 2;
range(t, mid - 10, mid + 10) {
if (!valid(t, l, r)) continue;
djikstra(t, l, lefta);
djikstra(t, r, righta);
for (auto query: queries) {
if (query.first > t || query.second < t) continue;
if (lefta[query.first] == infinity || righta[query.second] == infinity) continue;
ans[query.idx] = min(ans[query.idx], lefta[query.first] + righta[query.second]);
}
}
vector<Query> hehe[2];
for (auto query: queries) {
if (query.first <= mid && query.second >= mid) continue;
hehe[query.first > mid].push_back(query);
}
dac(l, mid, hehe[0]);
dac(mid + 1, r, hehe[1]);
}
void solve() {
range(i, 0, 10001) ans[i] = infinity;
sher(), n = sher(), m = sher();
int q = sher();
adj = new vector<pair<int, int>>[n];
range(i, 0, m) {
int a = sher(), b = sher(), t = sher();
// edge[a][b - a] = t;
adj[b].emplace_back(a, t);
adj[a].emplace_back(b, t);
}
vector<Query> queries;
range(i, 0, q) {
int a = sher(), b = sher();
if (a > b) swap(a, b);
queries.push_back({a, b, i});
}
dac(0, n - 1, queries);
range(i, 0, q) {
if (queries[i].first == queries[i].second) {
print("0");
continue;
}
int x = ans[i];
if (x == infinity) print("-1");
else print(x);
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("marathon.in", "r", stdin);
// freopen("marathon.out", "w", stdout);
//#ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
//#endif
// sieve(1000001);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
