#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<vector>
#include<stdio.h>
#include<map>
#include<set>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include<bitset>
using namespace std;
const int N=5e5+5;
int n,m,k,q;
int head[N],to[N*2],nex[N*2],w[N*2],cnt;
void add(int u,int v,int ww){
	cnt++;
	to[cnt]=v;
	nex[cnt]=head[u];
	w[cnt]=ww;
	head[u]=cnt;
}
struct node{
	int id,w;
	friend bool operator<(node a,node b){
		return a.w>b.w;
	}
};
int dis[N];
void djkstra(){
	node book;
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0;
	book.w=0;book.id=0;
	priority_queue<node>q;
	q.push(book);
	while(!q.empty()){
		book=q.top();q.pop();
		for(int i=head[book.id];i;i=nex[i]){
			int y=to[i];
			if(dis[y]>book.w+w[i]){
				dis[y]=book.w+w[i];
				node book2;book2.id=y;book2.w=dis[y];
				q.push(book2);
			}
		}
	}
}
struct abc{
	int a,b,w;
}z[N*2];
int tot;
bool cmp(abc a,abc b){
	return a.w<b.w;
}
int cha[N];
int find(int x){
	if(cha[x]==x)return x;
	cha[x]=find(cha[x]);
	return cha[x];
}
vector<int>g[N],ww[N];
int fa[N][25],c[N][25];
int deep[N];
void dfs(int x,int f){
	deep[x]=deep[f]+1;
	for(int i=1;i<=log2(deep[x]);i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
		c[x][i]=max(c[fa[x][i-1]][i-1],c[x][i-1]);
	}
	for(int i=0;i<g[x].size();i++){
		int v=g[x][i];
		if(v==f)continue;
		c[v][0]=ww[x][i];
		dfs(v,x);
	}
}
int lca(int x,int y){
	if(deep[y]>deep[x])swap(x,y);
	int d=deep[x]-deep[y];
	int ans=0;
	for(int i=0;i<=19;i++){
		if(d&(1<<i)){
			ans=max(ans,c[x][i]);
			x=fa[x][i];
			if(deep[x]==deep[y])break;
		}
	}
	if(x==y)return x;
	for(int i=log2(deep[x]);i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			ans=max(ans,max(c[x][i],c[y][i]));
			x=fa[x][i];y=fa[y][i];
		}
	}
	return max(ans,max(c[x][0],c[y][0]));
}
int main(){
	cin>>n>>m>>k>>q;
	for(int u,v,ww,i=1;i<=m;i++){
		cin>>u>>v>>ww;
		add(u,v,ww);add(v,u,ww);
	}
	for(int i=1;i<=k;i++){
		add(0,i,0);
	}
	djkstra();
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nex[j]){
			w[j]+=dis[i]+dis[to[j]];
			z[++tot].a=i;z[tot].b=to[j];z[tot].w=w[j];
		}
	}
	sort(z+1,z+1+tot,cmp);
	int block=n;
	for(int i=1;i<=n;i++)cha[i]=i;
	for(int i=1;i<=tot;i++){
		if(block==1)break;
		if(find(z[i].a)!=find(z[i].b)){
			cha[find(z[i].a)]=find(z[i].b);
			g[z[i].a].push_back(z[i].b);
			ww[z[i].a].push_back(z[i].w);
			g[z[i].b].push_back(z[i].a);
			ww[z[i].b].push_back(z[i].w);
			block--;
		}
	}
	dfs(1,0);
	while(q--){
		int u,v;
		cin>>u>>v;
		cout<<lca(u,v)<<endl;
	}
	return 0;
}