#include <bits/stdc++.h>
using namespace std;
bool b[1001];
int n,m,s,a[1001][1001],Min[1001];
void Dijkstra()
{
	for(int i=1;i<=n;i++)
		Min[i]=a[s][i];
	Min[s]=0;
	b[s]=1;
	for(int i=1;i<n;i++)
	{
		int tmin=99999999,k=0;
		for(int j=1;j<=n;j++)
			if(!b[j]&&tmin>Min[j])
			{
				tmin=Min[j];
				k=j;
			}
		if(k==0)
			break;
		b[k]=1;
		for(int j=1;j<=n;j++)
		{
			if(Min[j]>Min[k]+a[k][j])
				Min[j]=Min[k]+a[k][j];
		}
	}	
}
int main()
{
	memset(a,0x03030303,sizeof(a));		
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		a[u][v]=w;
	}
	Dijkstra();
	for(int i=1;i<=n;i++)
		cout<<Min[i]<<" ";
	return 0;
}