#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
struct edge {
	int v, w;
};
vector<edge> g[MAXN];
long long dis[MAXN];
bool vis[MAXN];
struct gragh {
	int x;
	bool operator > (const gragh &b) const {return dis[x] > dis[b.x];}
};
int main() {
	int n, m, s;
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back({ v, w });
	}
	for (int i = 0; i < MAXN; i++)
		dis[i] = 100000000000000ll, vis[i] = false;
	dis[s] = 0;
	priority_queue< gragh, vector<gragh>, greater<gragh> >q;
	q.push({s});
	while (!q.empty()) {
		int x = q.top().x;
		q.pop();
		if (vis[x])
			continue;
		vis[x] = true;
		for (edge ed : g[x])
			if (dis[ed.v] > dis[x] + ed.w) {
				dis[ed.v] = dis[x] + ed.w;
				q.push({ed.v});
			}
	}
	for (int i = 1; i <= n; i++)
		printf("%lld ", dis[i]);
	return 0;
}