#include<iostream>
#include<cstdio>
#include<queue>
 
using namespace std;
 
long int n,m,s,mid,mid1,dist[100050],head1[100050];
struct data
{
    long int head,to,w;
};
bool operator <(data a,data b)
    { 
        return a.w>b.w;
    }
data dick,edge[200050];
priority_queue <data> q;
void init()
{
    scanf("%ld%ld%ld",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%ld%ld%ld",&mid,&edge[i].to,&edge[i].w);
        edge[i].head=head1[mid];
        head1[mid]=i;
    }
}
void dis()
{
    for(int i=1;i<=n;i++) dist[i]=0x7fffffff;
    dist[s]=0;dick.w=0;dick.head=s;q.push(dick);
    while(!q.empty())
    {
        dick=q.top();q.pop();
        //cout<<dick.head<<endl;
        mid=dick.head;mid1=head1[mid];
        if(dick.w!=dist[mid]) continue;
        while(mid1)
        {
            if(dist[edge[mid1].to]>dist[mid]+edge[mid1].w)
            {
                dist[edge[mid1].to]=dist[mid]+edge[mid1].w;
                dick.head=edge[mid1].to;dick.w=dist[edge[mid1].to];
                q.push(dick);
            }
            mid1=edge[mid1].head;
        }
    }
    
}
int main()
{
    init();
    dis();
    for(int i=1;i<=n;i++) printf("%ld ",dist[i]);
}