#include<bits/stdc++.h>
using namespace std;
long long i,j,n,m,s,u,v,w,flag[1000005],dis[1000005],e[10005][10005];
long long min_d;
long long U;
long long inf=1234567890;
void Dijkstra()
{
	for(i=1;i<=n-1;i++)
	{
		min_d=inf;
		for(j=1;j<=n;j++)
		{
			if(flag[j]==0&&dis[j]<min_d)
			{
				min_d=dis[j];
				U=j;
			}
		}
		flag[U]=1;
		for(j=1;j<=n;j++)
		{
			if(e[U][j]<inf)
			{
				if(dis[j]>dis[U]+e[U][j])
					dis[j]=dis[U]+e[U][j];
			}
		} 
	}
}
int main()
{
	cin>>n>>m>>s;
	memset(flag,0,sizeof(flag));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				e[i][j]=0;
			else
				e[i][j]=inf;
	for(i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		e[u][v]=min(e[u][v],w);
	}
	for(i=1;i<=n;i++)
		dis[i]=e[s][i];
	for(i=1;i<=n;i++)
		flag[i]=0;
	flag[s]=1;
	Dijkstra();
	for(i=1;i<=n;i++)
		cout<<dis[i]<<' ';
	return 0;
}