#include<bits/stdc++.h>

using namespace std;

const int N=10010;

int dist[N];
int g[N][N];
int st[N];//1表示该点最短路已确定 

void dijkstra(int s,int n){
	memset(dist ,0x3f,sizeof dist);
	dist[s]=0;
//如果先把起点s放入st集合中，
//会导致没有用起点去更新它的出边 
//	st[s]=1;
	for(int i=1;i<=n;i++)//循环n次 确保dist数组每个元素都存入最小值 
	{
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[t]>dist[j])){
				t=j;
			}
		}
		st[t]=1;
		for(int j=1;j<=n;j++){
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		//	printf("*******%d\n",dist[j]);
			
		}
//		printf("--------\n") ;
	}
}

int main(void){
	int n,m,s;
	cin>>n>>m>>s;
	memset(g,0x3f,sizeof g);
	while(m--){
		int x,y,w;
		cin>>x>>y>>w;		
		g[x][y]=min(g[x][y],w);	
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			printf("-------%d\n",g[i][j]);
//		}
//	}
	dijkstra(s,n);
	for(int i=1;i<=n;i++){
		if(dist[i]==0x3f3f3f3f){
			cout<<2147483647<<' ';
		}
		else{
			cout<<dist[i]<<' '; 		
		}
//		cout<<dist[i]<<' ';
	}
	return 0;
}