#include<bits/stdc++.h>
using namespace std;
const int N=1005,INF=0x3f3f3f3f;
int n,m;
int g[N][N],dist[N],p[N],f[N];
void init()
{
	memset(g,0x3f,sizeof(g));
	memset(dist,0x3f,sizeof(dist));
	memset(p,-1,sizeof(p));
	memset(f,0,sizeof(f));
}
void dijkstra(int u)
{
	dist[u]=0;
	for(int j=1;j<=n;j++)
	{
		int mn=INF,t=INF;
		for(int i=1;i<=n;i++)
		{
			if(!f[i]&&dist[i]<mn)
			{
				mn=dist[i];
				t=i;
			}		 
		}
		if(t==INF)return;
		f[t]=1;
		for(int i=1;i<=n;i++)
		{
			if(g[t][i]+dist[t]<dist[i]&&!f[i]&&g[t][i]!=INF)
			{
				dist[i]=g[t][i]+dist[t];
				p[i]=t;
			}	
		}
	}
}
int main()
{
	int u,v,w,s;
	cin>>n>>m>>s;
	init();
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		g[u][v]=w;
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<dist[i]<<' ';
	}
}

0分求调