#include"bits/stdc++.h"
	using namespace std;
	int n, m, s;
	int idx;
	long long  ver[200010], nxt[100010], head[100010],val[200010],dis[100010],tf[100010];
	struct node {
		int a,b;
		bool  operator < (const node& x)  const {
			return a>x.a;
		}
	};
	priority_queue<node>q;
	void add(int u,int v,int w) {
		val[++idx] = w;
		ver[idx] = v;
		nxt[idx] = head[u];
		head[u] = idx;
	}
	void dijkstra() {
		q.push({0,s});
		while (q.size()) {
			node u = q.top();
			q.pop();
			if (tf[u.b] == 1) {
				continue;
			}
			tf[u.b] = 1;
			for (int i = head[u.b]; i; i = nxt[i]) {
				int v = ver[i];
				if (dis[v] > dis[u.b] + val[i]) {
					dis[v] = dis[u.b] + val[i];
					node neww;
					neww.a = dis[v], neww.b = v;
					q.push(neww);
				}
				}
			}
		}
	int main() {
		memset(dis, 0x3f, sizeof(dis));
		cin >> n >> m >> s;
		dis[s] = 0;
		for (int i = 1; i <= m; i++) {
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
		}
			dijkstra();
			for (int j = 1; j <= n; j++) {
				cout << dis[j]<<' ';
			}
		return 0;
	}