#include<bits/stdc++.h>
using namespace std;
int f[10001][10001];

bool b[10000];
int c[10001];
int n,x,y,m,s,e,k,r,minl,maxx=1e9;
int main()
{cin>>n>>m>>r;
for (int i=1;i<=n;i++)
{
	for (int j=1;j<=n;j++)
	{
		f[i][j]=1e9;
	}
}
for (int i=1;i<=m;i++)
{cin>>x>>y>>s;
if (f[x][y]>s)
f[x][y]=s;}

memset(b,false,sizeof(b));
b[r]=true;
c[r]=0;
for (int i=1;i<=n;i++)
c[i]=f[r][i];
for (int i=1;i<=n-1;i++)
{minl=maxx;
k=0;
for (int j=1;j<=n;j++)
{if ((!b[j])&&(c[j]<minl))
{minl=c[j];
k=j;}}
if (k==0)
break;
b[k]=true;
for (int j=1;j<=n;j++)
{if (c[k]+f[k][j]<c[j])
c[j]=c[k]+f[k][j];}}
for (int i=1;i<=n;i++)
{if (c[i]==1e9)
cout<<"0 ";
else
cout<<c[i]<<" ";}
return 0;//样例过了}