#include<bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;
const int N=1e4+5;
int n,m,s,u,v,w,dis[N],maps[N][N];
bool check[N];
int main()
{
	memset(dis,inf,sizeof(dis));
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		maps[u][v]=w;
	}
	dis[s]=0;
	for(int i=1;i<=n;i++)
	{
		int minc=inf,minx;
		for(int j=1;j<=n;j++)
		{
			if(dis[j]<minc&&check[j]==0)
			{
				minc=dis[j];
				minx=j;
			}
		}
		check[minx]=1; 
		for(int j=1;j<=n;j++)
		{
			if(maps[minx][j]>0)
			{
				if(minc+maps[minx][j]<dis[j])
				{
					dis[j]=minc+maps[minx][j];
				}
			}
		 } 
	}
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==inf)
		{
			cout<<2147483646<<" "; 
		}
		else
		{
			cout<<dis[i]<<" ";
		}
	}
	return 0;
}