#include<bits/stdc++.h>
#define maxn 120000
using namespace std;
int head[maxn];
int n,m,s;
int dis[maxn],book[maxn];
struct Edge
{
	int to;
	int next;
	int w;
}e[maxn*2];
int k=0;
void adde(int u,int v,int w)
{
	k++;
	e[k].to=v;
	e[k].w=w;
	e[k].next=head[u];
	head[u]=k;
}
struct ndui
{
	int id,diss;
	ndui(int id1,int dis1) 
	{
		id=id1;
		diss=dis1;
	}
	friend bool operator <(ndui x,ndui y)
	{
		x.diss>y.diss;
	}
};
priority_queue<ndui> q;
void dijkstra()
{
	
	int u=s;
	for(int j=1;j<n;j++)
	{
		book[u]=1;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(book[v])continue;
			if(dis[u]+e[i].w<dis[v])
			{
				dis[v]=dis[u]+e[i].w;
				q.push(ndui(v,dis[v]));
			}
		}
		while(q.size()>0&&book[q.top().id])q.pop();
		u=q.top().id;
		q.pop();
	}
}
int main()
{
	cin>>n>>m>>s;
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		adde(u,v,w);
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0; 
	dijkstra();
	for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
	return 0;
}