#include <bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define _for(i, a, b) for(int i = a; i <= b; i++) 
#define pii pair<ll, ll>
using namespace std;
const ll N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f;
ll n, m, s, idx, h[N], dist[N], vis[N];
struct edge {
	ll e, w, next;
}edges[N];

void add(ll a, ll b, ll c) {
	edges[idx].e = b; edges[idx].w = c; edges[idx].next = h[a]; h[a] = idx++;
	return ;
}
void dijkstra() {
	dist[s] = 0;
	priority_queue<pii, vector<pii>, greater<pii> > heap;
	heap.push({0, s});
	while(heap.size()) {
		ll t = heap.top().second, dis = heap.top().first; heap.pop();
		if(vis[t]) continue; vis[t] = 1;
		for(int i = h[t]; i != -1; i = edges[i].next) {
			int j = edges[i].e, distance = edges[i].w;
			if(dist[j] > dis + distance) {
				dist[j] = dis + distance;
				heap.push({dist[j], j});
			}
		}
	}
	return ;
}
int main() {
	IOS;
	cin >> n >> m >> s;
	memset(h, -1, sizeof h);
	memset(dist, inf, sizeof dist);
	_for(i, 1, m) {
		ll a, b, c; cin >> a >> b >> c;
		add(a, b, c);
	}
	dijkstra();
	_for(i, 1, n) {
		if(dist[i] > inf / 2) cout << pow(2, 31) - 1;
		else cout << dist[i];
		cout << " "; 
	}
	return 0;
}