#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline

using namespace std;

il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
return x * f; }

const int M = 500005, N = 10005, INF = 0x3f3f3f;
int n, m, s, dis[N], head[N], cnt;

struct edge {
	int pre, v, w;
}e[M];;

struct node {
	int s, now;
	bool operator < (const node &X) const {
		return s > X.s;
	}
};
priority_queue<node> q;

il void add(int U, int V, int W) {
	e[++ cnt].pre = head[U];
	e[cnt].v = V;
	e[cnt].w = W;
	head[U] = cnt;
}

int main() {
	n = read(), m = read(), s = read();
	for(re int i = 1; i <= m; ++ i) {
		re int U = read(), V = read(), W = read();
		add(U, V, W);
	}
	for(int i = 1; i <= n; ++ i) dis[i] = INF;
	dis[s] = 0;
	q.push((node){0, s});
	while(!q.empty()) {
		re node x = q.top();
		q.pop();
		int u = x.now;
		for(re int i = head[u]; i; i = e[i].pre){
			int v = e[i].v;
			if(dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				q.push((node){dis[v], v});
			}
		}
	}
	for(re int i = 1; i <= n; ++ i) {
		printf("%d ", dis[i]);
	}
	return 0;
}