#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    register int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48); 
        c=getchar();
    }
    return x*f;
}
const int maxn=1e5+10;
const int maxm=2e5+10;
const int inf=0x7f;
struct edge
{
    int dis,next,to;
}a[maxm];
struct node
{
    int d,p;//d是距离，u是当前节点  
    bool operator <( const node &x )const
    {
        return x.d<d;
    }
};
int dis[maxn],head[maxn],n,m,s,cnt;
bool vis[maxn];
priority_queue<node>q;
void addedge(int u,int v,int w)
{
	cnt++;
	a[cnt].dis=w;
	a[cnt].to=v;
	a[cnt].next=head[u];
	head[u]=cnt;
}
int main()
{
	n=read(),m=read(),s=read();
	for(int i=1;i<=n;i++) dis[i]=inf;
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		addedge(u,v,w);
	}
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int u=tmp.p;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[i];i;i=a[i].next)
		{
			if(dis[a[i].to]>dis[u]+a[i].dis)
			{
				dis[a[i].to]=dis[u]+a[i].dis;
				if(!vis[a[i].to])
					q.push((node){dis[a[i].to],a[i].to});	
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
	return 0;
}