#include<iostream>
using namespace std;
int n,m,start;
struct node{
	int w,next,t;
}e[600005];
bool b[500005];
long long int head[500005],total,d[500005];
int add(int s,int t,int w)
{
	e[++total].w=w;
	e[total].t=t,e[total].next=head[s];
	head[s]=total;
}
int main()
{
	freopen("1.in","r",stdin);
	cin>>n>>m>>start;
	int s,t,w;
	for(int i=1;i<=m;i++)
	{
		cin>>s>>t>>w;
		add(s,t,w);
	}
	for(int i=1;i<=n;i++)
	{
		d[i]=2147483647;
	}
	d[start]=0;
	bool flag=1;
	int maxx,k;
	while(flag)
	{
		flag=0,maxx=2147483647,k=0;
		for(int i=1;i<=n;i++)
		{
			if(!b[i]&&d[i]<maxx)
				maxx=d[i],k=i;
		}
		if(k==0)
			break;
		b[k]=1;
		int x=head[k];
		while(x)
		{
			if(d[e[x].t]>d[k]+e[x].w)
			{
				d[e[x].t]=d[k]+e[x].w;
				flag=1;
			}
			x=e[x].next;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<d[i]<<" ";
	}
	return 0;
}