#include <iostream>
#define max (1<<31)-1
using namespace std;
int n,m,s,u,v,w,mid,gragh[10001][10001],min_dis,dist[10001],vist[10001],i,j;
int dijkstra()
{
	for(j=1;j<=n;j++)
		dist[j]=gragh[s][j];
	for(i=1;i<=n;i++)
	{
		min_dis=max,mid=1;
		for(j=1;j<=n;j++)
		{
			if(!vist[j]&&min_dis>dist[j])
				min_dis=dist[j],mid=j;
		}
		for(j=1;j<=n;j++)
		{
			if(!vist[j]&&(gragh[mid][j]!=max)&&dist[j]>min_dis+gragh[mid][j])
				dist[j]=min_dis+gragh[mid][j];
		} 
		vist[mid]=1;
		cout << dist[i]<<" ";
	}
		
	return 0;
}
int main()
{
	cin >> n>> m>> s;
	vist[s]=1;
	for(i=1;i<=m;i++)
	{
		cin >> u>> v>> w;
		gragh[u][v]=w;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			if(gragh[i][j]==0) gragh[i][j]=max;
		gragh[i][i]=0;
	}
	dijkstra();
	
	
	return 0;
}