#include<bits/stdc++.h>
using namespace std;

int mp[11000][110];
bool f[1000000];
int dis[1000000];
int main(){
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		mp[u][v]=w;
	}
	
	for(int i=0;i<=n+2;i++){//初始化 
		dis[i]=20000000;
	}
	
	dis[s]=0;
	int mn=21000000;
	int number=0;
	
	for(int x=1;x<n;x++){
		mn=21000000;
		for(int i=1;i<=n;i++){
			if(mn>dis[i]&&f[i]==false){
				number=i;//目前起点 
				mn=dis[i];
			}
		}
		f[number]=true;	
		for(int i=1;i<=n;i++){
			dis[i]=min(mp[number][i]+dis[number],dis[i]);
		}
	
	}
	for(int i=1;i<=n;i++){
		if(!f[i])cout<<2147483647<<' ';
		else cout<<dis[i]<<' ';
	}
	
//	dijkstra(num);
	
}