#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=5e5+5;
struct Edge
{
	int to,w,next;
}edge[M];
int tot=0,head[N];
int n,m,s;
void add(int u,int v,int w)
{
	edge[++tot].to=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot;
}
int siz[N];bool vis[N];
struct Heap
{
	int sum,id;
}heap[M];
int tail=0;
void push(int k,int x)
{
	heap[++tail].id=k;
	heap[tail].sum=x;
	int son=tail,fa=tail/2;
	while(fa&&heap[fa].sum>heap[son].sum)
	{
		swap(heap[son],heap[fa]);
		son=fa;fa=son/2;
	}
}
void pop()
{
	heap[1]=heap[tail--];
	int fa=1,son=fa*2;
	while(son<=tail)
	{
		if(heap[son+1].sum<heap[son].sum&&son<=tail)son++;
		if(heap[fa].sum<=heap[son].sum)break;
			swap(heap[fa],heap[son]);
		fa=son;son=fa*2;
	}
}
void dij(int s)
{
	memset(siz,0x3f,sizeof siz);
	siz[s]=0;push(s,0);
	for(int i=1;i<=n;i++)
	{
		int minsiz=heap[1].id;
	//	printf("min:%d %d\n",minsiz,siz[minsiz]);
		pop();
		if(vis[minsiz]==1) continue;
	//	printf("2min:%d %d\n",minsiz,siz[minsiz]);
		vis[minsiz]=1;
		for(int i=head[minsiz];i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(siz[v]>siz[minsiz]+edge[i].w)
			{
				siz[v]=siz[minsiz]+edge[i].w;
				push(v,siz[v]);
		//		printf("push:%d %d\n",v,siz[v]);
			} 
		}
	}
}
int main()
{
	scanf("%d %d %d",&n,&m,&s);
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
	}
	dij(s);
	for(int i=1;i<=n;i++)
	if(siz[i]<0x3f3f3f3f)printf("%d ",siz[i]);
	else cout<<(1ll<<31)-1<<" ";
}
/*
5 16 1
1 2 1
1 4 3
1 5 4
2 1 1
2 3 3
2 4 1
2 5 1
3 2 3
3 5 1
4 1 3
4 2 1
4 5 1
5 1 4
5 2 1
5 3 1
5 4 1
*/