#include<bits/stdc++.h>
using namespace std;
long long a[10000][10000],n,m,s,dis[10000],t[10000];
void dij()
{
	for(int i=1;i<n;i++)
	{
		long long litle=2147483647,zhongzhuan;
		for(int j=1;j<n;j++)
		{
			if(litle>dis[j] && t[j]==0)
			{
				zhongzhuan=j;
				t[j]=1;
				break;
			}
		}
		for(int j=1;j<=n;j++)
		{
			if(t[j]==1)
				continue;
			else
			{
				dis[j]=min(dis[j],dis[zhongzhuan]+a[zhongzhuan][j]);
			}
		}
//							for(int i=1;i<=n;i++)
//							{
//								for(int j=1;j<=n;j++)
//								{
//									cout<<a[i][j]<<' ';
//								}
//								cout<<endl;
//							}
//							cout<<endl;
//							for(int i=1;i<=n;i++)
//							{
//								cout<<dis[i]<<' ';
//							}
//							cout<<endl;
//							for(int i=1;i<=n;i++)
//							{
//								cout<<t[i]<<' ';
//							}
//							cout<<endl<<endl;
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=0;i<=n;i++)
	for(int j=0;j<=n;j++)
	a[i][j]=2147483647;
	a[s][s]=0;
	for(int i=1;i<=m;i++)
	{
		
		long long x,y,z;
		cin>>x>>y>>z;
		a[x][y]=min(a[x][y],z);
	}
	for(int i=1;i<=n;i++)
		dis[i]=a[s][i];
//						for(int i=1;i<=n;i++)
//						{
//							for(int j=1;j<=n;j++)
//							{
//								cout<<a[i][j]<<' ';
//							}
//							cout<<endl;
//						}
//						cout<<endl;
//						for(int i=1;i<=n;i++)
//						{
//							cout<<dis[i]<<' ';
//						}
//						cout<<endl<<endl;
	dij();
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<' ';
	cout<<endl;
	return 0;
}