#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n,m,t[100005],le,ri,ti,head[100005],length[100005],num[100005],N,first;bool visit[100005];
struct node
{
	int location,time;
}q[1000005];
struct edge
{
	int ri,cost,next;
};
edge Edge[500005];
void pushpriorityqueue(int num,int location,int time)
{
	while(time<q[num/2].time&&num!=1)
	{
		q[num].location=q[num/2].location;
		q[num].time=q[num/2].time;
		num/=2;
	}
	q[num].location=location;
	q[num].time=time;
}
void poppriorityqueue()
{
	int location=1;
	--n;
	while((2*location==n&&q[2*location].time<q[n].time)||(2*location+1<=n&&(q[2*location].time<q[n].time||q[2*location+1].time<q[n].time)))
	{
		if(2*location==n)
		{
			q[location].time=q[2*location].time;
			q[location].location=q[2*location].location;
			location=2*location;	
		}
		else
		{
			if(q[2*location].time<q[2*location+1].time)
			{
				q[location].time=q[2*location].time;
				q[location].location=q[2*location].location;
				location=2*location;
			}
			else
			{
				q[location].time=q[2*location+1].time;
				q[location].location=q[2*location+1].location;
				location=2*location+1;
			}
		}
	}
	q[location].location=q[n+1].location;
	q[location].time=q[n+1].time;
}
int main()
{
	cin>>n>>m>>first;
	N=n;
	for(int i=1;i<=n;i++)
		length[i]=-1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&le,&ri,&ti);
		Edge[i].ri=ri;
		Edge[i].cost=ti;
		Edge[i].next=head[le];
		head[le]=i;
	}
	length[first]=0;
	q[1].location=first;
	while(n)
	{
		int point=q[1].location,now=0;
		poppriorityqueue();
		if(visit[point]) continue;
		else visit[point]=1;
		visit[point]=1;
		for(int j=head[point];j!=0;j=Edge[j].next)
		{
			if(length[Edge[j].ri]<0||length[Edge[j].ri]>=length[point]+Edge[j].cost)
			{
				if(length[Edge[j].ri]==length[point]+Edge[j].cost)
				{
					num[Edge[j].ri]+=num[point];
				}
				else num[Edge[j].ri]=num[point];
				num[Edge[j].ri]%=1000000007;
				length[Edge[j].ri]=length[point]+Edge[j].cost;
				++n;
				pushpriorityqueue(n,Edge[j].ri,length[Edge[j].ri]);
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		if(length[i]!=-1) printf("%d ",length[i]);
		else cout<<2147483647<<" ";
	}
	return 0;
}