#include<bits/stdc++.h>
using namespace std;
const int MM=200005; 
int tot,cnt,now,n,m,s,u,v,w,dis[MM],vis[MM],head[MM],nxt[MM*2],to[MM*2],q[MM*2];
struct cmp
{
	bool operator()(int a,int b)
	{
		return dis[a]>dis[b]; 
	} 
};
priority_queue<int, vector<int>, cmp>qu;
void add(int u,int v,int w)
{
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	q[tot]=w;
}
int main()
{
	memset(dis,0x3f,sizeof(dis));
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
		cin>>u>>v>>w,add(u,v,w),add(v,u,w);
	dis[s]=0;
	qu.push(s);
	while(!qu.empty())
	{
		now=qu.top();
		qu.pop();
		vis[now]=1;
		cnt++;
		for(int i=head[now];i;i=nxt[i])
			if(dis[now]+q[i]<dis[to[i]])
			{
				dis[to[i]]=dis[now]+q[i];
				qu.push(to[i]);
			}
	}
	for(int i=1;i<=n;i++)	
		cout<<dis[i]<<' ';
	return 0;
}

最短路板子