#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=500010;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
struct edge
{
    int to,dis,next;
}e[M];
int head[N],dis[N],cnt;
bool vis[N];
int n,m,s;
inline void add_edge(int u,int v,int d )
{
    cnt++;e[cnt].next = head[u];e[cnt].to = v;e[cnt].dis = d;head[u] = cnt;  
}
struct node
{
    int dis,pos;
    bool operator<(const node &x)const{return x.dis<dis;}
};
priority_queue<node> q;
inline void dijkstra()
{
    dis[s]=0;
    q.push((node){0,s});
    while(!q.empty())
    {
        node tmp=q.top();q.pop();
        int x=tmp.pos,d=tmp.dis;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].next)
        {
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].dis)
            {
                dis[y]=dis[x]+e[i].dis;
                if(!vis[y]) q.push((node){dis[y],y});
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;++i)  dis[i]=0x7fffffff;
    for(register int i=0;i<m;++i)
    {
        register int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        add_edge(u,v,d);
    }
    dijkstra();
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}