#include<iostream>
#include<cstring>
#include<cmath>
const long long N = 500001, M = 2147483647;
using namespace std;

struct node {
	long next, to, w;
}edge[N];
int n, m, s, cnt = 0, head[N];
long long dis[N];
bool vis[N]; 

void add(int u, int v, int w) {
	edge[++cnt].next = head[u];
	edge[cnt].to = v;
	edge[cnt].w = w;
	head[u] = cnt;
}

inline int read() {
	/*register*/ long x = 0, f = 1;
	/*register*/ char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') {
			f = -1;
			c = getchar();
		}
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + (c - 48);
		c = getchar();
	}
	return x * f;
}

void dijkstra() {
	for (int i = 1; i <= n; i++) {
		dis[i] = M;
	}
	dis[s] = 0;
	for (int i = 1; i <= n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && (dis[t] > dis[j] || t == -1)) {
				t = j;
			}
		}
		vis[t] = 1;
		for (int j = head[t]; j; j = edge[j].next) {
			dis[edge[j].to] = min(dis[edge[j].to], edge[j].w + dis[t]);
		}
	}
}

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