#include<bits/stdc++.h>
#define ll long long int
const int N=1e7+7;
const int inf=2147483647;
using namespace std;
ll n,m,s;
struct map{
	ll to,next,w;
}edge[2*N];
ll cnt=0,head[N],sizem=0;
ll hm[4*N],pd[N],dis[N];
void add_edge(ll u,ll v,ll w){
	cnt++;
	edge[cnt].to=v,edge[cnt].w=w,edge[cnt].next=head[u],head[u]=cnt;
}
void insterm(ll point,ll x){
	sizem++;
	hm[sizem]=point;
	dis[point]=min(dis[point],x);
	ll pos=sizem;
	while (pos!=1){
		if (dis[hm[pos]]>=dis[hm[pos/2]]){
			break;
		}
		else{
			swap(hm[pos],hm[pos/2]);
		}
		pos/=2;
	}
}
void delm(){	
	hm[1]=hm[sizem],sizem--;
	ll now=1;
	while (now*2<=sizem){
		ll next=now*2;
		if (next+1<=sizem && dis[hm[next+1]]<dis[hm[next]]){
			next++;
		}
		if (dis[hm[now]]>dis[hm[next]]){
			swap(hm[now],hm[next]);
		}
		if (dis[hm[now]]<=dis[hm[next]]){
			break;
		}
		now=next;
	}
}
void dijkstra(){
	for (ll i=1;i<=n;i++){
		dis[i]=inf;
		pd[i]=0;
	}
	dis[s]=0;
	for (ll i=head[s];i!=0;i=edge[i].next){
		insterm(edge[i].to,edge[i].w);
	}
	while (sizem!=0){
		ll top=hm[1];
		delm();
		if (pd[top]==1) continue;
		pd[top]=1;
		for (ll i=head[top];i!=0;i=edge[i].next){
			ll j=edge[i].to;
			if (dis[j]>dis[top]+edge[i].w){
				dis[j]=dis[top]+edge[i].w;
				insterm(j,dis[j]);
			}
		}
	}
}
int main()
{
    cin>>n>>m>>s;
    for (ll i=1;i<=m;i++){
		ll x,y,w;
		cin>>x>>y>>w;
		add_edge(x,y,w);
	}
	dijkstra();
	for (ll i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
    return 0;
}