#include<cstring>
#include<queue>
#include<iostream>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010; 

struct edge{
    int ne,to,w;
}e[N*5];

bool vis[N]; 

int n,m,s,idx,dis[N],h[N];

void add(int a,int b,int c){
    e[++idx].to=b;
    e[idx].ne=h[a];
    e[idx].w=c;
    h[a]=idx;
}

struct node { 
    int dis; 
    int pos; 
    bool operator <( const node &x )const { 
        return x.dis < dis; 
    } 
}; 
priority_queue<node> q; 

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 = h[x]; i; i = e[i].ne ) { 
            int y = e[i].to; 
            if( dis[y] > dis[x] + e[i].w ) { 
                dis[y] = dis[x] + e[i].w; 
                if( !vis[y] ) 
                    q.push((node){dis[y], y});  
            } 
        } 
    } 
} 

int main()
{
    scanf("%d%d%d", &n, &m,&s);
    memset(dis,0x3f,sizeof(dis));
    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }
    dijkstra(); 
    for( int i = 1; i <= n; i++ ) 
        printf( "%d ", dis[i] ); 
    return 0;
}