#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10;
int n, m, s;
int dis[MAXN];
int vis[MAXN];
vector< pair<int, int> > p[MAXN];
set< pair<int, int> > q;
void dijkstra(int s) {
	for (int i = 1; i <= n; i++)
		dis[i] = INT_MAX;
	dis[s] = 0;
	for (int i = 1; i <= n; i++)
		q.insert(make_pair(dis[i], i));
	while (!q.empty()) {
		int x = q.begin()->second;
		q.erase(q.begin());
		if (x > 1 << 30) break;
		for (int i = 0; i < p[x].size(); i++) {
			int v = p[x][i].first;
			int w = p[x][i].second;
			if (dis[v] > dis[x] + w) {
				q.erase(make_pair(dis[v], v));
				dis[v] = dis[x] + w;
				q.insert(make_pair(dis[v], v));
			}
		}
	}
	for (int i = 1; i <= n; i++)
		cout << dis[i] << " ";
	return;
}
int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		p[x].push_back(make_pair(y, w));
	}
	dijkstra(s);
	return 0;
}