#include <iostream>
#include <queue>
#include <cstdio>
#define int long long

using namespace std;

const int N = 1e5 + 1, Inf = 1e18;

int n, m, k;
struct edge {
	int v, w, next;
} e[2 * N];
int head[N];
int cnt;
struct node {
	int ans, id;
	bool operator <(const node &x) const {
		return x.ans > ans;
	}
};
priority_queue<node> q;
int dis[N];
bool vis[N];

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

signed main() {
	scanf("%lld%lld%lld", &n, &m, &k);
	for (int i = 1; i <= n; i ++ )
		dis[i] = Inf;
	dis[k] = 0;
	for (int i = 1; i <= m; i ++ ) {
		int u, v, w;
		scanf("%lld%lld%lld", &u, &v, &w);
		add(u, v, w);
	}
	int u;
	q.push(node {0, k});
	while (!q.empty()) {
		u = q.top().id;
		q.pop();
		if (vis[u])
			continue;
		vis[k] = true;
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if (dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				if (!vis[v])
					q.push(node {dis[v], v});
			}
		}
	}
	for (int i = 1; i <= n; i ++ )
		printf("%d ", dis[i]);
	return 0;
}