#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define N 100009
#define M 400009
struct node{long long to,val,nxt;}edge[M];
priority_queue<pair<long long,long long>>q;
long long n,m,s,u,v,w,cnt,dis[N],vis[N],head[N];
void dijistra()
{
	memset(dis,0x3f,sizeof(dis)),dis[s]=0;
	q.push(mp(0,s));
	while(!q.empty())
	{
		pair<long long,long long> u=q.top();q.pop();
		if(vis[u.second]) continue;
		vis[u.second]=1;
		for(int i=head[u.second];i!=-1;i=edge[i].nxt)
		{
			node v=edge[i];
			if(dis[u.second]+v.val<dis[v.to])
			{
				dis[v.to]=dis[u.second]+v.val;
				if(!vis[v.to]) q.push(mp(-dis[v.to],v.to));
			}
		}
	}
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&s);
	memset(head,-1,sizeof(head));
	for(long long i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&u,&v,&w);
		edge[++cnt]={v,w,head[u]},head[u]=cnt;
		edge[++cnt]={u,w,head[v]},head[v]=cnt;
	}
	dijistra();
	for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
	return 0;
}

如上，玄2关