#include<bits/stdc++.h>
using namespace std;
void add(int u,int v,int w,int i);
void dijkstra();

const int N=1e5+2,M=2e5+2;
struct edge{
    int dis,to,next;
}e[M];
int n,m,s,u,v,w,head[N],dist[N];
priority_queue<pair<int,int> >pq;
bool t[N];

int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w,i);
    }
    for(int i=1;i<=n;i++)
        dist[i]=0x7fffffff;
    dijkstra();
    for(int i=1;i<=n;i++)
        cout<<dist[i]<<" ";
    return 0;
}
void add(int u,int v,int w,int i)
{
    e[i].dis=w;
    e[i].to=v;
    e[i].next=head[u];
    head[u]=i;
}
void dijkstra()
{
    dist[s]=0;
    pq.push(make_pair(s,0));
    while(!pq.empty())
    {
        u=pq.top().first;
        pq.pop();
        if(t[u])
            continue;
        t[u]=1;
        for(int i=head[u];i;i=e[i].next)
            if(dist[u]+e[i].dis<dist[e[i].to])
            {
                dist[e[i].to]=dist[u]+e[i].dis;
                pq.push(make_pair(e[i].to,-dist[e[i].to]));
            }
    }
}