#include<fstream>
using namespace std;
fstream fin("d.in",ios::in),fout("d.out",ios::out);
int n,m,a[50001][50001],x,y,c,infinit,start,pmin,i,j,k,p[50001],v[50001],d[50001];
void drum(int nod)
{
	if(p[nod]!=0)
	{
		drum(p[nod]);
		//fout<<nod<<" ";
	}
	return;
}

int pminim(int infinit)
{
	int i,minim;
	pmin=0;minim=infinit;
	for(i=1;i<=n;i++)
	{
		if(v[i]==0 && d[i]<minim)
		{
			minim=d[i];
			pmin=i;
		}
	}
	return pmin;
}

int main()
{
	fin>>n>>m>>start;
	memset(a,5,sizeof(a));
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		a[x][y]=c;
	}
	infinit=a[0][0];
	for(i=1;i<=n;i++)
	{
		d[i]=a[start][i];
		if(d[i] != infinit )
			p[i]=start;
	}
	d[start]=0;
	p[start]=0;
	v[start]=1;
	
	for(k=1;k<=n-1;k++)
	{
		pmin=pminim(infinit);
		if(pmin==0)
			break;
		v[pmin]=1;
		for(i=1;i<=n;i++)
		{
			if(d[i]>d[pmin]+a[pmin][i])
			{
				d[i]=d[pmin]+a[pmin][i];
				p[i]=pmin;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		if(d[i] != infinit)
			drum(i);
		
	}
	for(i=1;i<=n;i++)
	{
		fout<<d[i]<<" ";
	}
	
fin.close();
fout.close();
return 0;
}