#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10;
int n, m, s;
struct node {
	int v, w;
};
vector <node> g[N];
int dis[N];
bool vis[N];
int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= n; i++) dis[i] = 2e9;
	for (int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		g[u].push_back({v, w});
	}
	priority_queue <int, vector <int>, greater <int> > q;
	dis[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int u = q.top();
		q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i].v, w = g[u][i].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!vis[v]) q.push(v);
			}
		}
	}
	for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
	return 0;
}