RT

#include<bits/stdc++.h>
#define ll long long

int innum(char c){return ('0'<= c && c <='9');}

using namespace std;
ll read(){
	ll res = 0, f = 1;
	char c = getchar();
	while(!innum(c)){if(c =='-')f = -1; c = getchar();}
	while( innum(c)){res = res * 10 + (c ^ 48);c = getchar();}
	return res * f;
}

void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	} 
	if(x == 0){
		putchar('0');
		return;
	}
	char res[22] = {};
	int t = 0;
	for(; x; x /= 10){res[t++] = (x % 10) ^ 48;}
	while(t){putchar(res[--t]);}
}

void writeln(ll x, char end = '\n'){
	write(x);
	putchar(end);
}

const int N = 500022;
const ll inf = 2147483647;
ll dis[N];

int head[N], to[N], cost[N], nxt[N], tot, n;
int vis[N];

int add(int f, int t, int c){
	to[++tot] = t;
	cost[tot] = c;
	nxt[tot] = head[f];
	head[f] = tot;
}

struct way{
	int csum, to;
	friend bool operator < (way a, way b){
		return a.csum > b.csum;
	}
}tmp;

priority_queue<way> q;

void pushin(int c, int t){
	tmp.csum = c;
	tmp.to = t;
	q.push(tmp);
}

int dijkstra(int s){
	for(int i = 0; i <= n; i++)dis[i] = inf;
	dis[s] = 0;
	pushin(0, s);
	for(;!q.empty();){
		int u = q.top().to;
		q.pop();
		if(vis[u]++)continue;
		for(int p = head[u]; p; p = nxt[p]){
			if(dis[u] + cost[p] < dis[to[p]]){
				dis[to[p]] = dis[u] + cost[p];
				pushin(dis[to[p]], to[p]);
			}
		} 
	}
}

int main(){
	n = read();
	int m = read(), s = read();
	for(int i = 0, u, v, w; i < m; i++){
		u = read();
		v = read();
		w = read();
		add(u, v, w);
	}
	dijkstra(s);
	for(int i = 1; i <= n; i++){
		writeln(dis[i], ' ');
	}
	return 0;
}

/*

4 6 1
1 2 2
1 3 5
1 4 4
2 3 2
2 4 1
3 4 3

*/