#include<bits/stdc++.h>
using namespace std;
int n,m,s,u,v,vis[1005];
long long a[1005][1005],d[1000],w;
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;++i) d[i]=(1<<31)-1;
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%lld",&u,&v,&w);
		a[u][v]=min(a[u][v],w);
	}
	d[s]=0;
	for(int i=1;i<=n;++i)
	{
		int now=0;
		for(int j=1;j<=n;++j)
			if(!vis[j]&&(now==0||d[j]<d[now]))
				now=j;
		vis[now]=1;
		for(int j=1;j<=n;++j)
			if(!vis[j]&&d[j]>d[now]+a[now][j])
				d[j]=d[now]+a[now][j];
	}
	for(int i=1;i<=n;++i) cout<<d[i]<<' ';
	return 0;
}