#include<stdio.h>
long long e[10010][10010],dis[10010],book[10010];
int main(void){
	long long s,n,t1,t2,t3,u,v,min;
	long long m,i,j;
	int inf=99999999;
	scanf("%lld%lld%lld",&n,&m,&s);
	for(i=1;i<=n;i++){
		for( j=1;j<=n;j++){
			if(i==j)
				e[i][j]=0;
			else 
				e[i][j]=inf;
		}
	}
	for(i=1;i<=m;i++){
		scanf("%lld%lld%lld",&t1,&t2,&t3);
		if(e[t1][t2]>t3){
			e[t1][t2]=t3;
		} 
	}
	for(i=1;i<=n;i++){
		dis[i]=e[s][i];
	}
	for(i=1;i<=n;i++){
		book[i]=0;
	}
	book[s]=1;
	for(i=1;i<=n;i++){
		min=inf;
		for(int j=1;j<=n;j++){
			if(book[j]==0&&dis[j]<min){
				min=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(v=1;v<=n;v++){
			if(e[u][v]<inf){
				if(dis[v]>dis[u]+e[u][v])
				dis[v]=dis[u]+e[u][v];
			}
		}
	}
	for(i=1;i<=n;i++){
		if(i==1)printf("%lld",dis[i]);
		else printf(" %lld",dis[i]);
	}
	return 0;
}