#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MM=300005; 
ll tot,cnt,now,n,m,s,u,v,w,dis[MM],vis[MM],head[MM],nxt[MM*2],to[MM*2],q[MM*2];
struct cmp
{
    bool operator()(int a,int b)
    {
        return dis[a]>dis[b]; 
    } 
};
priority_queue<int, vector<int>, cmp>qu;
void add(int u,int v,int w)
{
    nxt[++tot]=head[u];
    head[u]=tot;
    to[tot]=v;
    q[tot]=w;
}
int main()
{

    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
        cin>>u>>v>>w,add(u,v,w);
    for(int i=1;i<=n;i++)
        dis[i]=0x7fffffff;
    dis[s]=0;
    qu.push(s);
    while(!qu.empty())
    {
        now=qu.top();
        qu.pop();
        if(vis[now])
            continue;
        vis[now]=1;
        for(int i=head[now];i;i=nxt[i])
        {
            if(dis[now]+q[i]<dis[to[i]])
            {
                dis[to[i]]=dis[now]+q[i];
                if(!vis[to[i]])
                    qu.push(to[i]);
            }
        }
    }
    for(int i=1;i<=n;i++)   
        cout<<dis[i]<<' ';
    return 0;
}