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

const int INF = 1 << 31 - 1;
int n, m, s, u, v, w, ans[10010];
map<int, int> edge[10010];

int main() {
	scanf("%d%d%d", &n, &m, &s);
	s--;
	while (m--) {
		scanf("%d%d%d", &u, &v, &w);
		u--;
		v--;
		if (edge[u].count(v) && edge[u][v] > w || !edge[u].count(v)) {
			edge[u][v] = w;
		}
	}
	for (int i = 0; i < n; i++) {
		ans[i] = INF;
	}
	ans[s] = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int p = q.front();
		for (auto i : edge[p]) {
			if (ans[p] + i.second < ans[i.first]) {
				ans[i.first] = ans[p] + i.second;
				q.push(i.first);
			}

		}
		q.pop();
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", ans[i]);
	}
}