#include <bits/stdc++.h>
using namespace std;
#define name "optcost"
#define MAXN 100005
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
u+=v;
if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
u-=v;
if (u<0) u+=MOD;
}
void minimize(int &u, int v){
u=min(u,v);
}
void maximize(int &u, int v){
u=max(u,v);
}
long long Rand(long long l, long long r){
ll tmp=0;
FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
return l+tmp%(r-l+1);
}
int k,n,m,q;
struct Edge{
int x,y,w;
}e[MAXN];
ii query[MAXN];
vector<ii> adj[MAXN];
namespace task1{
int len;
int root[MAXN];
int depth[MAXN];
int times=0;
ii cnt[MAXN];
const int LOG=15;
int anc[MAXN][LOG+1];
void dfs(int u){
root[u]=len;
cnt[u].fs=++times;
for (ii pairs:adj[u]){
int v=pairs.fs,w=pairs.sc;
depth[v]=depth[u]+w;
anc[v][0]=u;
dfs(v);
}
cnt[u].sc=times;
}
bool check_ancestor(int u, int v){
return cnt[u].fs<=cnt[v].fs&&cnt[v].fs<=cnt[u].sc;
}
int lca(int u, int v){
if (check_ancestor(u,v)) return u;
if (check_ancestor(v,u)) return v;
FORD(i,LOG,0) if (anc[u][i]&&!check_ancestor(anc[u][i],v)) u=anc[u][i];
return anc[u][0];
}
void solve(){
memset(root,-1,sizeof(root));
FOR(i,1,n){
if (root[i]==-1){
++len;
dfs(i);
}
}
FOR(j,1,LOG) FOR(i,1,n) anc[i][j]=anc[anc[i][j-1]][j-1];
FOR(id,1,q){
int u=query[id].fs,v=query[id].sc;
if (root[u]!=root[v]){
cout<<-1<<"\n";
}
else{
cout<<depth[u]+depth[v]-2*depth[lca(u,v)]<<"\n";
}
}
}
}
namespace task2{
bool mark[MAXN];
map<int, int> d[MAXN];
int in[MAXN];
void dfs(int u){
for (ii pairs:adj[u]){
int v=pairs.fs;
++in[v];
dfs(v);
}
}
queue<int> Q;
void calc(int p){
dfs(p);
Q.push(p);
while (Q.size()){
int u=Q.front();
Q.pop();
for (ii pairs:adj[u]){
int v=pairs.fs;
int w=pairs.sc;
if (d[p][v]==0||d[p][v]>d[p][u]+w) d[p][v]=d[p][u]+w;
if (--in[v]==0) Q.push(v);
}
}
}
void solve(){
FOR(i,1,q) mark[query[i].fs]=1;
FOR(i,1,n){
if (mark[i]) calc(i);
}
FOR(i,1,q){
int u=query[i].fs,v=query[i].sc;
if (u==v){
cout<<0<<"\n";
}
else{
cout<<(d[u][v]==0?-1:d[u][v])<<"\n";
}
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>k>>n>>m>>q;
FOR(i,1,m) cin>>e[i].x>>e[i].y>>e[i].w;
FOR(i,1,q) cin>>query[i].fs>>query[i].sc;
FOR(i,1,m){
++e[i].x;
++e[i].y;
}
FOR(i,1,q){
++query[i].fs;
++query[i].sc;
}
FOR(i,1,m){
adj[e[i].x].pb({e[i].y,e[i].w});
}
if (k==1) task1::solve();
else task2::solve();
return 0;
}
