#include<bits/stdc++.h>
using namespace std;
#define INF 65535
int n,m,s;//点个数，边个数，出发点
int graph[10001][10001];
int dis[10001];
int pre[10001];
bool vist[10001];

void read(){
	cin>>n>>m>>s;
	//初始化
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			graph[i][j]=INF;
	//读入边
	for(int i=1;i<=m;i++){
		int v1,v2;
		cin>>v1>>v2;
		cin>>graph[v1][v2];
	} 
}

void dijkstra(){
	//初始化dist和pre加vist 
	for(int i=1;i<=n;i++){
		vist[i]=false;
		pre[i]=-1;//-1表示没有路
		dis[i]=graph[s][i]; 
	} 
	
	//收录起点
	vist[s]=true; 
	pre[s]=s;
	dis[s]=0;
	
	while(1){
		int mind=INF;
		int minv;
		//寻找目前可去的没去过的最短点,没有则退出
		for(int i=1;i<=n;i++){
			if(vist[i]==false&&dis[i]<mind){
				mind=dis[i];
				minv=i;
			}
		}
		if(mind==INF) break;
		
		//收录i结点
		vist[minv]=true;
		//更新其他结点
		for(int i=1;i<=n;i++){
			//若没访问过且出现更短路径则更新
			if(vist[i]==false&&dis[i]>dis[minv]+graph[minv][i]){
				dis[i]=dis[minv]+graph[minv][i];
				pre[i]=minv;
			} 
		}
	} 
}

int main(void){
	//录入数据
	read();
	//dijkstra
	dijkstra();
	//打印 
	for(int i=1;i<n;i++){
		if(dis[i]==INF) cout<<pow(2,31)-1<<" ";
		else cout<<dis[i]<<" ";
	}
	if(dis[n]==INF) cout<<pow(2,31)-1;
	else cout<<dis[n];
	return 0;
}