rt，模拟赛数据过了，CF上寄了（

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#pragma optimize("Ofast") 
#define N 1000001
#define ll long long
#define MAXN 1e16

using namespace std;

int n,m,k,T,tot,cnt;
ll dis[N * 5],a[N * 5];
int top[N * 5],siz[N * 5],son[N * 5],s[N * 5][2],hd[N * 5],dep[N * 5],f[N * 5],fa[N * 5];

struct E
{
	int u,v,nxt;
	ll w;
}e1[N * 5],e2[N * 5];

void add1( int u , int v , ll w )
{
	tot ++;
	e1[tot].v = v;
	e1[tot].w = w;
	e1[tot].nxt = hd[u];
	hd[u] = tot;
}

void add2( int u , int v , ll w )
{
	tot ++;
	e2[tot].u = u;
	e2[tot].v = v;
	e2[tot].w = w;
}

void dijk( void )
{
	priority_queue<ll,vector<pair<ll,int> >,greater<pair<ll,int> > > q; 
	int u,v;
	for( int i = 1 ; i <= n ; i ++ )
		dis[i] = MAXN;
	for( int i = 1 ; i <= k ; i ++ )
	{
		dis[i] = 0;
		q.push( make_pair( dis[i] , i ) );
	}
	while( !q.empty() )
	{
		u = q.top().second;
		q.pop();
		for( int i = hd[u] ; i ; i = e1[i].nxt )
		{
			v = e1[i].v;
			if( dis[u] + e1[i].w < dis[v] )
			{
				dis[v] = dis[u] + e1[i].w;
				q.push( make_pair( dis[v] , v ) );
			}
		}
	}
	return;
}

bool cmp( E x , E y )
{
	return x.w < y.w;
}

int lca( int u , int v )
{
	while( top[u] != top[v] )
	{
		if( dep[top[u]] >= dep[top[v]] )
			u = fa[top[u]];
		else
			v = fa[top[v]];
	}
	if( dep[u] > dep[v] ) swap( u , v );
	return u;
}

void dfs1( int u , int ff )
{
	dep[u] = dep[ff] + 1;
	siz[u] = 1;
	fa[u] = ff;
	int v;
	v = s[u][0];
	if( s[u][0] )
	{
		dfs1( v , u );
		siz[u] += siz[v];
		if( siz[v] > siz[son[u]] )
			son[u] = v;
	}
	v = s[u][1];
	if( s[u][1] )
	{
		dfs1( v , u );
		siz[u] += siz[v];
		if( siz[v] > siz[son[u]] )
			son[u] = v;
	}
	return;
}

void dfs2( int u , int ff , int flag )
{
	if( flag ) top[u] = u;
	else top[u] = top[ff];
	if( son[u] ) dfs2( son[u] , u , 0 );
	if( s[u][0] && s[u][0] != son[u] ) dfs2( s[u][0] , u , 1 );
	if( s[u][1] && s[u][1] != son[u] ) dfs2( s[u][1] , u , 1 );
	return;
}

int cx( int x )
{
	if( x == f[x] ) return x;
	return f[x] = cx( f[x] );
}

ll read( void )
{
	ll x = 0,f = 1;
	char ch = getchar();
	while( ch < '0' || ch > '9' ) ch = getchar();
	while( ch >= '0' && ch <= '9' ) x = x * 10 + ch - '0',ch = getchar();
	return x * f;
}

int main()
{
	int u,v,w;
	cin >> n >> m >> k >> T;
	for( int i = 1 ; i <= n ; i ++ )
		f[i] = i;
	for( int i = 1 ; i <= m ; i ++ )
	{
		u = read(),v = read(),w = read();
		add1( u , v , w );
		add1( v , u , w );		
	}
	cnt = n;
	dijk();
	tot = 0;
	for( u = 1 ; u <= n ; u ++ )
	{
		for( int i = hd[u] ; i ; i = e1[i].nxt )
		{
			v = e1[i].v;
			if( u < v )
			add2( u , v , dis[u] + dis[v] + e1[i].w );
		}
	}
	sort( e2 + 1 , e2 + m + 1 , cmp );
	for( int i = 1 ; i <= m ; i ++ )
	{
		u = cx( e2[i].u ),v = cx( e2[i].v );
		if( u == v ) continue;
		cnt ++;
		f[u] = f[v] = f[cnt] = cnt;
		s[cnt][0] = u,s[cnt][1] = v;
		a[cnt] = e2[i].w;
	}
	dfs1( cnt , 0 );
	dfs2( cnt , 0 , 1 );
	while( T -- )
	{
		u = read(),v = read();
		printf( "%lld\n" , a[lca( u , v )] );
	}
	return 0;
}