#include "bits/stdc++.h"
using namespace std;

struct Edge {
	int to, nxt, dis;
};

struct Node {
	int x, dis;
	bool operator < (const Node& p) const {
		return x > p.x;
	}
};

Edge e[1919810];
int hd[1919810], dis[1919810], vis[1919810];
int n, m, s, cnt;

void Add_Edge(int u, int v, int d) {
	++cnt;
	e[cnt].dis = d;
	e[cnt].to = v;
	e[cnt].nxt = hd[u];
	hd[u] = cnt;
}

priority_queue<Node> q;

void Dijkstra() {
	for (int i = 0; i < 1919810; ++i) dis[i] = 0x3f3f3f3f;
	dis[s] = 0;
	Node al, be;
	al.dis = 0; al.x = s;
	q.push(al);
	while (!q.empty()) {
		be = q.top();
		q.pop();
		int u, v, di;
		u = be.x; di = be.dis;
		if (vis[u]) continue;
		vis[u] = 1;
		
		for (int i = hd[u]; i; i = e[i].nxt) {
			v = e[i].to;
			if (dis[v] > dis[u] + e[i].dis) {
				dis[v] = dis[u] + e[i].dis;
				if (!vis[v]) {
					al.x = v; al.dis = dis[v];
					q.push(al);
				}
			}
		}
	}
}

int main() {
	scanf ("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= m; ++i) {
		int u, v, d;
		scanf ("%d%d%d", &u, &v, &d);
		Add_Edge(u, v, d);
	}
	Dijkstra();
	for (int i = 1; i <= n; ++i) printf ("%d ", dis[i]);
}