#include <queue> 
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 500005
#define ll long long
using namespace std;
priority_queue< ll,vector<ll>,greater<ll> > q;

inline ll fread(){
	ll f=1ll,k=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')
			f=-1ll;
		c=getchar();
	}
	while(isdigit(c)){
		k=k*10ll+(c-48);
		c=getchar();
	}
	return f*k*1ll;
}

void fwrite(ll x){
	if(x<0){
		x=~x+1ll;
		putchar('-');
	}
	if(x>9)
		fwrite(x/10ll);
	putchar(x%10ll+48);
}

struct Edge{
	ll u;
	ll v;
	ll w;
	ll nex;
}E[maxn];
ll head[maxn],tote;
inline void add_edge(ll u,ll v,ll w){
	++tote;
	E[tote].u=u;
	E[tote].v=v;
	E[tote].w=w;
	E[tote].nex=head[u];
	head[u]=tote;
}

ll dis[maxn];
bool vis[maxn];

int main(){
	ll n=fread();
	ll m=fread();
	ll s=fread();
	for(ll i=1;i<=m;++i){
		ll x,y,z;
		x=fread();
		y=fread();
		z=fread();
		add_edge(x,y,z);
	}
	ll x;
	for(ll i=1;i<=n;++i)
		dis[i]=0x7f7f7f7f;
	dis[s]=0;
	q.push(s);
	/*for(int i=1;i<=n;++i){
		while(!q.empty()){
			x=q.top();
			q.pop();
			if(vis[x])
				continue;
			else
				break;
		}
		vis[x]=1;
		for(int j=head[x];j;j=E[j].nex){
			int v=E[j].v;
			int w=E[j].w;
			if(dis[v]>dis[x]+w){
				dis[v]=dis[x]+w;
				q.push(v);
			}
		}
	}*/
	while(!q.empty()){
		x=q.top();
		q.pop();
		if(vis[x])
			continue;
		vis[x]=1;
		for(ll i=head[x];i;i=E[i].nex){
			ll v=E[i].v;
			ll w=E[i].w;
			if(dis[v]>dis[x]+w){
				dis[v]=dis[x]+w;
				q.push(v); 
			}
		}
	}
	for(ll i=1;i<=n;++i){
		fwrite(dis[i]);
		putchar(' ');
	}
	return 0;
}