#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
int K;
vector< vector< vector<int> > > mat;
vector< vector<int> > iden;
vii adj[50005];
struct node
{
vector< vector<int> > dat;
node *left, *right;
node(){}
node(vector< vector<int> > want, node *A, node *B)
{
dat.assign(K, vi(K, 0));
dat = want;
left = A, right = B;
}
};
node* build(int L, int R)
{
if(L == R) return new node(mat[L], NULL, NULL);
node* res = new node(vector< vector<int> >(K, vi(K, 0)), NULL, NULL);
res->left = build(L, (L+R)/2);
res->right = build((L+R)/2+1, R);
for(int i = 0; i< K; i++)
{
for(int j = 0; j< K; j++)
{
int best = 1e9;
for(int k = 0; k< K; k++)
{
best = min(best, res->left->dat[i][k]+res->right->dat[k][j]);
}
res->dat[i][j] = best;
}
}
return res;
}
node query(node* p, int L, int R, int i, int j)
{
//printf("it's %d %d %d %d\n", L, R, i, j);
if(i> R || j< L) return node(iden, NULL, NULL);
if(i<= L && R<= j) return *p;
node res(vector< vi >(K, vi(K, 0)), NULL, NULL);
node x = query(p->left, L, (L+R)/2, i, j);
node y = query(p->right, (L+R)/2+1, R, i, j);
//printf("here for %d %d\n", L, R);
for(int i = 0; i< K; i++)
{
for(int j = 0; j< K; j++)
{
int best = 1e9;
for(int k = 0; k< K; k++)
{
best = min(best, x.dat[i][k]+y.dat[k][j]);
}
res.dat[i][j] = best;
}
}
return res;
}
int main()
{
int n, m, q;
scanf("%d %d %d %d", &K, &n, &m, &q);
mat.assign(n/K+1, vector< vector<int> >(K, vi(K, 1e9)));
for(int i = 0; i< m; i++)
{
int a, b, w; scanf("%d %d %d", &a, &b, &w);
adj[a].pb(ii(b, w));
mat[a/K][a%K][b%K] = min(mat[a/K][a%K][b%K], w);
}
iden.assign(K, vi(K, 1e9));
for(int i = 0; i< K; i++) iden[i][i] = 0;
node *root = build(0, (n-1)/K-1);
//printf("ok\n");
while(q--)
{
int x, y; scanf("%d %d", &x, &y);
//kprintf("hihi\n");
if(x == y)
{
printf("0\n"); continue;
}
if(x> y) swap(x, y);
int x1 = x/K, x2 = x%K;
int y1 = y/K, y2 = y%K;
if(x1 == y1)
{
printf("-1\n"); continue;
}
node tmp = query(root, 0, (n-1)/K-1, x1, y1-1);
//printf("%d %d\n", x2, y2);
int res = tmp.dat[x2][y2];
if(res == 1e9) printf("-1\n");
else printf("%d\n", res);
/*
vector< vector<int>
> ans(K, vi(K, 0));
for(int p = x1; p< y1; p++)
{
vector< vector<int> > rub(K, vi(K, 1e9));
for(int i = 0; i< K; i++)
{
for(int j = 0; j< K; j++)
{
for(int k = 0; k< K; k++)
{
rub[i][j] = min(rub[i][j], ans[i][k]+mat[p][k][j]);
}
}
}
for(int i = 0; i< K; i++)
{
for(int j = 0; j< K; j++)
{
printf("%d ", rub[i][j]);
}
printf("\n");
}
for(int i = 0; i< K; i++) for(int j = 0; j< K; j++) ans[i][j] = rub[i][j];
}
int res = ans[x2][y2];
if(res == 1e9) printf("-1\n");
else printf("%d\n", res);
*/
}
return 0;
}
