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

#define ll long long
const long long inf = 2147483647;

struct adjnode {
	ll goal;
	ll w;
};

int main() {
	ll n, m, s;
	cin >> n >> m >> s;
	
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	vector<vector<adjnode>> adj(n + 1);
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> heap;
	vector<ll> dist(n + 1, inf);
	vector<ll> vis(n + 1, 1);
	

	for (int i = 1; i <= m; i++) {
		ll u, v, w;
		cin >> u >> v >> w;
		adjnode tmp;
		tmp.goal = v;
		tmp.w = w;
		adj[u].push_back(tmp);
	}
	
	dist[s] = 0;
	vis[s] = 0;
	heap.push({0, s});
	
	while (!heap.empty()) {
		ll start = heap.top().second;
		heap.pop();
		
		for (int i = 0; i < adj[start].size(); i++) {
			adjnode next = adj[start][i];
			ll new_dist = dist[start] + next.w;
			if (new_dist < dist[next.goal]) {
				dist[next.goal] = new_dist;
				heap.push({dist[next.goal], next.goal});
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		cout << dist[i];
		if (i != n) {
			cout << " ";
		}
	}
	
	return 0;
}