#include<bits/stdc++.h>
using namespace std;
struct node{
	int w,id;
};
node heap[5000005];
vector<vector<int>> edge,val;
int n,m,s,dis[100005],vis[100005],size;
void put(int x,int y){
	size++;
	heap[size].w=x;
	heap[size].id=y;
	int t=size;
	while(t>0){
		if(heap[t].w<heap[t/2].w) {
			swap(heap[t],heap[t/2]);
		    t=t/2;
		}else break;
	}
}
void deletee(){
	swap(heap[1],heap[size]);
	size--;
	int t=1;
	while(t*2<=size){
		int child=t*2;
		if(child<size && heap[child+1].w<heap[child].w) child++;
		if(heap[child].w<heap[t].w) {
			swap(heap[child],heap[t]);
		    t=child;
		}else break;
	}
}
int main(){
	cin>>n>>m>>s;
	edge.resize(n+1);
	val.resize(n+1);
	edge.clear();
	val.clear();
	int x,y,z,v,w;
	for(int i=1;i<=n;i++) dis[i]=214748367;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		edge[x].push_back(y);
		val[x].push_back(z);
	}
	size=0;
	put(0,s);
	dis[s]=0;
	for(int t=1;t<=n;t++){
		int u=heap[1].id;
		//cout<<edge[u].size()<<endl;
		deletee();
		while(vis[u]){
			u=heap[1].id;
			deletee();
		}
		vis[u]=1;
		for(int i=0;i<=edge[u].size()-1;i++){
			v=edge[u][i];
			w=val[u][i];
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				put(dis[v],v);
			}
			//cout<<i<<endl;
		}
	}
	dis[s]=0;
	for(int i=1;i<=n-1;i++) cout<<dis[i]<<' ';
	cout<<dis[n];
	return 0;
}