rt

#include<bits/stdc++.h>
#define inf 19198100
using namespace std;
int e[505][505];
int dis[505];
bool book[505];
int main()
{
	int n,m,s,u,v,w;
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) if(i==j) e[i][j]=0;else e[i][j]=inf;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		e[u][v]=w;
	}
	for(int i=1;i<=n;i++) dis[i]=e[s][i];
	memset(book,0,sizeof(book));
	book[1]=1;
	for(int i=1;i<n;i++)
	{
		int Min=inf;
		for(int j=1;j<=n;j++) if(!book[j]&&dis[j]<Min) Min=dis[j],u=j;
		book[u]=1;
		for(int v=1;v<=n;v++) if(e[u][v]<inf) if(dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v];
	}
	for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
	return 0;
}