[title]
CC
A graph of nnn points, in which there is an undirected edge of length xxx between the first kkk points. In addition, there are some undirected edges with the length of wiw ﹣ iwi ﹣.
Find the shortest circuit from SSS to all points.
n,k≤105n,k\leq 10^5n,k≤105

[solutions]
I don't know how I started to write about water.

We only need to connect the first kkk points with a new point TTT, x2\frac x 22x, and other edges.

The complexity O((n+k)log ⁡ K) O((n+k)log K) O ((n + k) logK) can be realized by multiplying all edge weights by 222, and finally dividing by 222 can avoid real numbers.

[reference code]

#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long ll;
typedef pair<ll,int> pii;
const int N=1e5+10;

int read()
{
	int ret=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
	return ret;
}
void write(ll x){if(x>9)write(x/10);putchar(x%10^48);}
void writesp(ll x){write(x);putchar(' ');}

namespace DreamLolita
{
	int n,K,X,m,S,tot;
	int head[N],vis[N];
	ll dis[N];
	priority_queue<pii,vector<pii>,greater<pii> >q;
	struct Tway{int v,w,nex;}e[N<<2];
	void add(int u,int v,int w)
	{
		e[++tot]=(Tway){v,w,head[u]};head[u]=tot;
		e[++tot]=(Tway){u,w,head[v]};head[v]=tot;
	}
	void dij()
	{
		dis[S]=0;q.push(mkp(dis[S],S));
		while(!q.empty())
		{
			int x=q.top().se;q.pop();
			if(vis[x])continue; vis[x]=1;
			for(int i=head[x];i;i=e[i].nex)
			{
				int v=e[i].v;
				if(!vis[v]) dis[v]=min(dis[v],dis[x]+e[i].w),q.push(mkp(dis[v],v));
			}
		}
	}
	void clear()
	{
		tot=0;
		memset(head,0,sizeof(head));memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));
	}
	void solution()
	{
		clear();
		n=read();K=read();X=read();m=read();S=read();
		for(int i=1,u,v;i<=m;++i) u=read(),v=read(),add(u,v,read()*2);
		for(int i=1;i<=K;++i) add(i,n+1,X); 
		dij();for(int i=1;i<=n;++i) writesp(dis[i]/2); puts("");
	}
}

int main()
{
#ifdef Durant_Lee
	freopen("CC_CLIQUED.in","r",stdin);
	freopen("CC_CLIQUED.out","w",stdout);
#endif
	int T=read();
	while(T--) DreamLolita::solution();
	return 0;
}