#include<bits/stdc++.h>
using namespace std;
int book[1001],e[1001][1001],dis[1001];
int i,j,n,m,inf=99999999,t1,t2,t3,s,f,u,miin;
int main(){
	
	cin>>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;
		}
	}//chushi
	for(j=1;j<=m;j++){
			cin>>t1>>t2>>t3;
			e[t1][t2]=t3;
	}//durubian
	for(i=1;i<=n;i++){
		dis[i]=e[s][i];
	}//dischushihua
	for(i=1;i<=n;i++){
		book[i]=0;
	}//chushihuabook
	book[s]=1;
	for(i=1;i<n;i++){
		 miin=inf;
		 for(j=1;j<=n;j++){
		 	if (book[j]==0&&dis[j]<miin) miin=dis[j];u=j;
			 }
			 book[u]=1;
			 for(j=1;j<=n;j++){
			 	if(e[u][j]+dis[u]<dis[j]&&e[u][j]<inf)//联通
				{
				 	dis[j]=dis[u]+e[u][j]; 
				} 
			 }
		 	
	}
	for(i=1;i<=n;i++) {
		cout<<dis[i]<<' ';
	}

	return 0;
}

rt，我感觉最近我脑抽