WA on #5

/*
*/
#include<bits/stdc++.h>
#define rep(i,s1,s2,s3) for(i = s1;i <= s2;i += s3)
#define r(i,s1,s2,s3) for(i = s1;i >= s2;i -= s3)
#define sort stable_sort
#define ull unsigned ll
#define INF 0x7f7f7f7f
#define ll long long
using namespace std;
ll n,m,k,qe,d[100010],fa[100010],lg[100010],dis[100010],f[100010][20],w[100010][20];
bool vis[100010];
struct node{
	ll u,v,w;
}e[300010];
struct edge{
	ll id,head[100010];
	struct node{
		ll u,v,w,next;
	}e[1200010];
	void add(ll u,ll v,ll w){
		e[++id] = node{u,v,w,head[u]};
		head[u] = id;
	}
}e1,e2;
struct ben{
	ll id,number;
	bool operator < (const ben &x) const{return x.number < number;}
};
priority_queue <ben> q;
void Dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	ll i;
	ben tmp,temp;
	rep(i,1,k,1) e1.add(i,0,0),e1.add(0,i,0);
	dis[0] = 0;
	q.push(ben{0,0}); 
	while(!q.empty()){
		tmp = q.top();
		q.pop();
		if(vis[tmp.id]) continue; 
		vis[tmp.id] = 1;
		for(i = e1.head[tmp.id];i;i = e1.e[i].next){
			if(dis[e1.e[i].v] > dis[tmp.id] + e1.e[i].w){
				dis[e1.e[i].v] = dis[tmp.id] + e1.e[i].w;
				if(!vis[e1.e[i].v]){
					temp.id = e1.e[i].v,temp.number = dis[e1.e[i].v];
					q.push(temp);
				}
			}
		}
	}
}
ll find(ll id){
	if(id == fa[id]) return id;
	return fa[id] = find(fa[id]);
}
bool cmp(node s1,node s2){
	return s1.w < s2.w;
}
void kruskal(){
	sort(e + 1,e + m + 1,cmp);
	ll i,cnt = 0;
	rep(i,1,n,1) fa[i] = i;
	rep(i,1,m,1){
		if(find(e[i].u) == find(e[i].v)) continue;
		fa[find(e[i].u)] = find(e[i].v);
		e2.add(e[i].u,e[i].v,e[i].w);
		e2.add(e[i].v,e[i].u,e[i].w);
		cnt++;
		if(cnt == n - 1) return ;
	}
}
void dfs(ll u,ll fa){
	f[u][0] = fa;
	for(ll i = e2.head[u];i;i = e2.e[i].next) if(e2.e[i].v != fa){
		d[e2.e[i].v] = d[u] + 1;
		w[e2.e[i].v][0] = e2.e[i].w;
		dfs(e2.e[i].v,u);
	}
}
ll lca(ll u,ll v){
	ll res = 0;
	if(d[u] < d[v]) swap(u,v);
	while(d[u] > d[v]){
		res = max(res,w[u][lg[d[u] - d[v]]]);
		u = f[u][lg[d[u] - d[v]]];
	}
	if(u == v) return res;
	ll i;
	r(i,lg[d[u]],0,1) if(f[u][i] != f[v][i]){
		res = max(res,max(w[u][i],w[v][i]));
		u = f[u][i],v = f[v][i];
	}
	return max(res,max(w[u][0],w[v][0]));
} 
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m>>k>>qe;
	ll i,j,u,v,w_;
	lg[0] = -1;
	rep(i,1,n,1) lg[i] = lg[n >> 1] + 1;
	rep(i,1,m,1){
		cin>>u>>v>>w_;
		e1.add(u,v,w_);
		e1.add(v,u,w_);
		e[i] = node{u,v,w_};
	}
	Dijkstra();
	rep(i,1,m,1)
		e[i].w += dis[e[i].u] + dis[e[i].v];
	kruskal();
	dfs(1,0);
	rep(j,1,lg[n],1) rep(i,1,n,1){
		f[i][j] = f[f[i][j - 1]][j - 1];
		w[i][j] = max(w[i][j - 1],w[f[i][j - 1]][j - 1]);
	}
//	rep(i,1,20,1){
//		rep(j,1,n,1) cout<<f[j][i]<<' ';
//		cout<<'\n';
//	}
//	rep(i,1,20,1){
//		rep(j,1,n,1) cout<<w[j][i]<<' ';
//		cout<<'\n';
//	}
	rep(i,1,qe,1){
		cin>>u>>v;
		cout<<lca(u,v)<<'\n';
	}
	return 0;
}