#include<stdio.h>
#include<stdlib.h>
typedef struct Edge{
    int dest;
    int w;
    struct Edge *next;
}Edge;
typedef struct Node{
    int key;
    struct Edge *edge;
}Node;
Node queue[500005];
int size=0;
int n,m,k,flag;
int dist[500005], vis[500005];
Node vertex[500005];
void push_up(){
    int i=size;
    Node temp=queue[i];
    while(i>1 && dist[temp.key]<dist[queue[i/2].key]){
        queue[i]=queue[i/2];
        i/=2;
    }
    queue[i]=temp;
}
void push_down(){
    int i=1;
    Node temp=queue[i];
    while(2*i<=size){
        int j=2*i;
        if(j!=size&&dist[queue[j].key]>dist[queue[j+1].key]) j++;
        if(dist[queue[j].key]<dist[temp.key]){
            queue[i]=queue[j];
            i=j;
        }
        else break;
    }
    queue[i]=temp;
}
void push(Node x){
    queue[++size]=x;
    push_up();
}
Node pop(){
    Node x=queue[1];
    queue[1]=queue[size--];
    push_down();
    return x;
}
void create_node(int n){
    for(int i=1;i<=n;i++){
        vertex[i].key=i;
        vertex[i].edge=NULL;
    }
}
void add_edge(int a,int b,int c){
    Edge* edge=(Edge*)malloc(sizeof(Edge));
    edge->dest=b;
    edge->w=c;
    edge->next=vertex[a].edge;
    vertex[a].edge=edge;
}
void init(int s){
    for(int i=1;i<=n;i++) dist[i]=1e9+5;
    for(int i=1;i<=n;i++){
        vis[i]=0;
    }
    dist[s]=0;
    while(size) pop();
}
void dijkstra(int s){
    push(vertex[s]);
    while(size){
        Node x=pop();
        if(vis[x.key]) continue;
        vis[x.key]=1;
        for(Edge* edge=x.edge;edge;edge=edge->next){
            int v=edge->dest;
            if(vis[v]) continue;
            if(dist[v]>dist[x.key]+edge->w){
                dist[v]=dist[x.key]+edge->w;
                if(!vis[v]) push(vertex[v]);
            }
        }
    }
}
int main(){
    int s;
    scanf("%d%d%d",&n,&m,&s);
    create_node(n);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
    }
    init(s);
    dijkstra(s);
    for(int i=1;i<=n;i++){
        printf("%d ",dist[i]);
    }
    return 0;
}