#include<cstdio>
#include<algorithm>
using namespace std;
struct ed{
	long long u,val,nxt;
};
long long n,m,s,tot;
long long head[1000010],dis[1000010];
ed side[2000010];
bool mark[1000010];
void add(long long u,long long v,long long w){
	if(head[u])side[tot+1].nxt=head[u];
	head[u]=++tot;
	side[tot].u=v;
	side[tot].val=w;
}
void song_chi(long long pos){
	long long x=pos;
	pos=head[pos];
	while(side[pos].nxt){
		dis[side[pos].u]=min(dis[side[pos].u],dis[x]+side[pos].val);
		pos=side[pos].nxt;
	}
	dis[side[pos].u]=min(dis[side[pos].u],dis[x]+side[pos].val);
	mark[x]=1;
}
void get_ans(){
	for(long long i=1;i<=n;i++){
		if(i==1)mark[s]=1;
		else{
			long long u=0;
			for(long long j=1;j<=n;j++){
				if(!mark[j]&&(!u||dis[j]<dis[u]))u=i;
			}
			song_chi(u);
		}
	}
}
void put_ans(){
	for(long long i=1;i<=n;i++){
		printf("%lld ",dis[i]);
	}
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&s);
	for(long long i=1;i<=n;i++){
		dis[i]=2147483647;
	}
	dis[s]=0;
	for(long long i=0;i<m;i++){
		long long x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		if(x==s)dis[y]=z;
		add(x,y,z);
	}
	get_ans();
	put_ans();
	return 0;
}