#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, s;
vector<int> to(1), dis(1), nxt(1);
int head[maxn];
void add(int x, int y, int z){
	to.push_back(y), dis.push_back(z), nxt.push_back(head[x]);
	head[x] = to.size() - 1;
}vector<int> ans(maxn, INT_MAX);
bitset<maxn> vis;
multimap<int, int> mp;
void dijkstra(int s){
	ans[s] = 0;
	mp.insert(pair<int, int>(0, s));
	while(mp.size()){
		int x = mp.begin() -> second;
		mp.erase(mp.begin());
		if(vis[x])
			continue;
		for(int i = head[x]; i; i = nxt[i]){
			int y = to[i];
			if(ans[y] > ans[x] + dis[i])
				mp.insert(pair<int, int>(ans[y] = ans[x] + dis[i], y));
		}
	}
}signed main(){
	scanf("%d%d%d", &n, &m, &s);
	while(m--){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
	}dijkstra(s);
	for(int i = 1; i <= n; ++i)
		printf("%d ", ans[i]);
	return 0;
}