#include<bits/stdc++.h>
using namespace std;
struct node
{
	int num,xs;
	bool operator <(const node &a) const
	{
		return xs>a.xs;
	}
};
int n,m,s,head[200005],cnt,dis[200005];
int to[200005],nxt[200005],w[200005];
bool mark[200005];
priority_queue<node> q;
 
void jb(int u,int v,int numi)
{
	cnt++;
	to[cnt]=v;
	w[cnt]=numi;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	int u,v,numi;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&numi);
		jb(u,v,numi);
	}
	memset(dis,0x3f,sizeof dis);
	q.push({s,0});
	mark[s]=1;
	dis[s]=0;
	while(!q.empty())
	{
		node g=q.top();
		q.pop();
		mark[g.num]=1;
		for(int i=head[g.num];i>=1;i=nxt[i])
		{
			if(dis[to[i]]>g.xs+w[i])
			{
				dis[to[i]]=g.xs+w[i];
				if(!mark[to[i]])q.push({to[i],dis[to[i]]});
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",dis[i]);
	}
	return 0;
}

码风有点怪(。＿ 。)悲、