#include <iostream>
#include <cstdio>
#define BIG 10000000
using namespace std;
int n,m,s,d[100001],t[100001],len[5001][5001],a,b,c;
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=5000;i++)
		for(int j=1;j<=5000;j++)
			len[i][j]=BIG;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		len[a][b]=c;
	}
	for(int i=1;i<=n;i++)
		d[i]=len[s][i];
	d[s]=0;
	t[s]=1;
	for(int i=1;i<n;i++)
	{
		int v,mi=0x7fffffff;
		for(int j=1;j<=n;j++)
			if(t[j]==0&&d[j]<mi)
			{
				v=j;
				mi=d[j];
			}
		t[v]=1;
		for(int j=1;j<=n;j++)
			if(t[j]==0)
				if(d[v]+len[v][j]<d[j])
					d[j]=d[v]+len[v][j];
	}
	for(int i=1;i<=n;i++)
		if(d[i]==BIG) cout<<0x7fffffff<<' ';
		else cout<<d[i]<<' ';
	return 0;
}