#include<stdio.h>
int n,m,s,cnt=0;
int dis[10005],vis[10005],head[500005];
struct Edge
{
	int next;
	int to;
	int dis;
}edge[500005];
void add(int from,int to,int dis)
{
	edge[++cnt].next=head[from];
	edge[cnt].to=to;
	edge[cnt].dis=dis;
	head[from]=cnt;
}
void spfa()
{
	int q[10005];
	int front=0,rear=0;
	for(int i=1;i<=n;i++)
	{
		dis[i]=2147483647;
		vis[i]=0;
	}
	q[rear++]=s;
	dis[s]=0;
	vis[s]=1;
	while(front!=rear)
	{
		int u=q[front];
		front++;
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].dis)
			{
				dis[v]=dis[u]+edge[i].dis;
				if(vis[v]==0)
				{
					vis[v]=1;
					q[rear++]=v;
				}
			}
		}
	}
}
int main()
{
	scanf("%d %d %d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		int f,g,w;
		scanf("%d %d %d",&f,&g,&w);
		add(f,g,w);
	}
	spfa();
	for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
}