#include<bits/stdc++.h>
using namespace std;
int n, m, s, cnt = 0;
const int maxn = 1e7 + 10;
const int maxx = 1e6+10;
int dis[maxx], head[maxx];
bool vis[maxx];
struct Edge {
	int to;
	int next;
	int w;
} edge[maxn];
void add(int u, int v, int w) {
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt++;

}
struct node{
	int id;
	int dis;
	bool operator<(const node &a) const{
		return a.dis<dis;
		
	} 
};
priority_queue<node> dl;
int main() {
	memset(head , -1 , sizeof head) ;
	cin >> n >> m >> s;
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u,v,w); 
	}
	for(int i=1;i<=n;++i){
		dis[i] = 2147483647;
	}
	dis[s] = 0;
	dl.push((node){s,0});
	while(!dl.empty()){
		node temp = dl.top();
		dl.pop();
		int u = temp.id;
		if(!vis[u]){
			vis[u] = 1;
			for(int i = head[u];~i;i = edge[i].next){
				int v = edge[i].to;
				if(dis[v]>dis[u]+edge[i].w){
					dis[v] = dis[u]+edge[i].w;
					if(!vis[v]){
						dl.push((node){dis[v],v});
						
					}
				} 
			}
		}
		
	}
	for(int i=1;i<=n;++i){
		cout<<dis[i]<<" ";
	}
	return 0;
}