#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MaxEdge=500000;
const int MaxVex=200000;
int n,m,s,cnt;
int head[MaxVex+1];//head[i]第i个顶点的第一条边的edge数组下标
bool vis[MaxVex+1];//vis[i]表示第i个顶点最短路径是否已经确定
int dis[MaxVex+1];//dis[i]从s点到i点的最短路径长度 
struct Edge
{
	int to;
	int next;
	int dis;
} edge[MaxEdge+1];
void add_edge(int u,int v,int w)
{
	edge[++cnt].dis=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
struct node
{
	int dis;
	int pos;//顶点
	bool operator <(const node &x) const
	{
		return x.dis<dis;//小根堆 
	}
};
priority_queue<node> q;
void dijkstra()
{
	q.push((node){0,s});//把顶点插入到堆 
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		int x=t.pos;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i!=0;i=edge[i].next)
		{
			int y=edge[i].to;
			if(!vis[y]&&dis[y]>dis[x]+edge[i].dis)
			{
				dis[y]=dis[x]+edge[i].dis;
				q.push((node){dis[y],y});
			}
		}	
	} 
} 
int main()
{
	int u,v,w;
	ios::sync_with_stdio(0);	
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	memset(dis,127,sizeof(dis));
	dis[s]=0;	
	dijkstra();
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<' ';
	return 0;
}