#include<cstdio>
using namespace std;
struct
{
	int from,to,w,next;
}e[200001];
int h[100001],cnt=1,ans[100001],x[200001],y=1;
void add(int u,int v,int w)
{
	e[cnt].next=h[u];
	h[u]=cnt;
	e[cnt].from=u;
	e[cnt].to=v;
	e[cnt].w=w;
	cnt++;
}
void bfs()
{
	int i,z;
	for(i=0;i!=y;i=(i+1)%200001)
	{
		for(z=h[x[i]];z;z=e[z].next)
		{
			if(ans[e[z].to]>ans[e[z].from]+e[z].w)
			{
				ans[e[z].to]=ans[e[z].from]+e[z].w;
				x[y]=e[z].to;
				y=(y+1)%200001;
			}
		}
	}
}
void so(int u)
{
	int i,min,t;
	min=h[u];
	for(i=min;i;i=e[i].next)
		if(e[i].w<e[min].w)
			min=i;
	if(min!=h[u])
	{
		t=e[h[u]].from;
		e[h[u]].from=e[min].from;
		e[min].from=t;
		t=e[h[u]].to;
		e[h[u]].to=e[min].to;
		e[min].to=t;
		t=e[h[u]].w;
		e[h[u]].w=e[min].w;
		e[min].w=t;
	}
}
int main()
{
	int n,m,s,i,u,v,w;
	scanf("%d%d%d",&n,&m,&s);
	for(i=0;i<=100000;i++)
	{
		h[i]=0;
		ans[i]=0x7fffffff;
	}
	for(i=0;i<=200000;i++)
	{
		e[i].next=0;
		x[i]=0x7fffffff;
	}
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	for(i=1;i<=n;i++)
		so(h[i]);
	ans[s]=0;
	x[0]=s;
	bfs();
	for(i=1;i<=n;i++)
		printf("%d ",ans[i]);
    return 0;
}