#include<bits/stdc++.h>
using namespace std;
int dis[100005], s, n, m, u, v, w;

struct noode{
	int to;
	int nt;
	int num;
}dij[400005];

int cnt;
int head[100005];
bool vis[100005];


void add(int a, int b, int c){
	cnt ++;
	dij[cnt].to = b;
	dij[cnt].num = c;
	dij[cnt].nt = head[a];
	head[a] = cnt;
}

struct node{
    int ds;
    int ps;
    bool operator <( const node &x )const{
        return x.ds < ds;
    }
};

priority_queue<node> q;


void dj(){
	q.push( (node) {0, s} );
	while(!q.empty()){
        node tp = q.top();
        q.pop();
        int x = tp.ps, d = tp.ds;
        if(vis[x])
            continue;
        vis[x] = 1;
        for(int i = head[x]; i ; i = dij[i].nt){
            int y = dij[i].to;
            if(dis[y] > dis[x] + dij[i].num){
                dis[y] = dis[x] + dij[i].num;
                if(!vis[y])
                    q.push( ( node ) {dis[y], y} );
            }
        }
    }
}

int main(){
	scanf("%d%d%d", &n, &m, &s);
	for(int i = 1; i <= n; ++ i)
		dis[i] = 0x7ffffff;
	for(int i = 1; i <= m; ++ i){
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
	}
	
	dis[s] = 0;
	dj();
	for(int i = 1 ; i <= n ; ++ i)
		printf("%d ", dis[i]);
	return 0;
	
}