#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define f(i, n) for (ll i = 0; i < n; i++)
#define ia(a, n) \
ll a[n]; \
f(i, n) cin >> a[i]
#define iv(v, n) \
vector<ll> v(n); \
f(i, n) cin >> v[i]
#define MOD (1000000007)
#define INF 1000000000000000000LL // Infinity for ll
#define mp make_pair
#define nline '\n'
#define yes cout << "YES\n"
#define no cout << "NO\n"
template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// read question properly
// don't forget newlines!!!!!!
// take care about cin >> t;
// comment the optimization before debugging
// ALWAYS USE FIXED << SETPRECISION WHILE OUTPUTTING FLOATS
struct Mat
{
vector<vector<ll>> mat;
Mat() {}
void resize(int n)
{
mat.assign(n, vector<ll>(n, INF));
}
Mat operator+(const Mat &other)
{
ll n = mat.size();
assert(n == other.mat.size());
assert(n > 0);
Mat ans;
ans.resize(n);
f(i, n)
{
f(j, n)
{
ans.mat[i][j] = INF;
f(k, n)
{
ans.mat[i][j] = min(ans.mat[i][j], mat[i][k] + other.mat[k][j]);
}
}
}
return ans;
}
};
void solve()
{
ll k, n, m, o;
cin >> k >> n >> m >> o;
vector<array<ll, 3>> edges;
f(i, m)
{
ll a, b, t;
cin >> a >> b >> t;
edges.push_back({a, b, t});
}
ll g = (n + k - 1) / k;
ll L = log2(g);
vector<vector<Mat>> lift(L + 1, vector<Mat>(g));
f(i, g)
{
lift[0][i].resize(k);
}
for (auto &x : edges)
{
lift[0][x[0] / k].mat[x[0] % k][x[1] % k] = x[2];
}
for (ll i = 1; i <= L; i++)
{
f(j, g)
{
if (j + (1 << (i)) >= g)
break;
else
lift[i][j] = lift[i - 1][j] + lift[i - 1][j + (1 << (i - 1))];
}
}
while (o--)
{
ll a, b;
cin >> a >> b;
if (a == b)
{
cout << 0 << nline;
continue;
}
if (a > b)
{
cout << -1 << nline;
continue;
}
if (a / k == b / k)
{
cout << -1 << nline;
continue;
}
ll ga = a / k, gb = b / k;
Mat ans;
ans.resize(k);
f(i, k)
{
ans.mat[i][i] = 0;
}
for (ll i = L; i >= 0; i--)
{
if (gb - ga >= (1 << i))
{
ans = ans + lift[i][ga];
ga += (1 << i);
}
}
if (ans.mat[a % k][b % k] != INF)
{
cout << ans.mat[a % k][b % k] << nline;
}
else
{
cout << -1 << nline;
}
}
}
int main()
{
#ifdef PRADY
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
clock_t T = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long t = 1;
// cin >> t;
while (t--)
{
solve();
}
#ifdef PRADY
cout << "\nTime taken: " << ((float)(clock() - T)) / CLOCKS_PER_SEC << " seconds";
#endif
return 0;
}
