#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
struct node{
	ll nxt,to,w;
}g[N];
ll head[N],dis[N],vis[N];
ll n,m,s,cnt=1;
priority_queue<pair<ll,ll> > q;
void add(ll u,ll v,ll w){
	g[cnt].to=v;
	g[cnt].w=w;
	g[cnt].nxt=head[u];
	head[u]=cnt++;
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&s);
	for(int i=1;i<=m;i++){
		ll u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);
//		if(u==s) q.push(make_pair(v,w));
	}
	memset(dis,0x3f,sizeof(dis));
//	for(int i=head[s];i;i=g[i].nxt) dis[g[i].to]=g[i].w;
	dis[s]=0;
	vis[s]=1;
	q.push(make_pair(0,s));
	while(!q.empty()){
		ll u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=g[i].nxt){
			ll v=g[i].to,w=g[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(v,dis[v]));
			}
		}
	}
	for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
	return 0;
}