#include<iostream>  
using namespace std;
int n,m,s,u,v,w;
int a[10001][10001];
int dst[10110];
int vis[10010];
long long q=1;
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		a[u][v]=w;
	}
	for(int i=1;i<=31;i++)q=q*2;
	for(int i=1;i<=n;i++)dst[i]=1e9;
	dst[s]=0;
	for(int i=1;i<=n;i++){
		int h=-1;
		for(int j=1;j<=n;j++){
			if((h==-1||dst[h]>dst[i])&&!vis[i])h=i;
		}
		vis[h]=1;
		for(int i=1;i<=n;i++){
			if(dst[h]+a[h][i]<dst[i])dst[i]=a[h][i]+dst[h];
		}
	}
	for(int i=1;i<=n;i++){
		if(dst[i]==1e9)cout<<q-1<<" ";
		else cout<<dst[i]<<" ";
	}	
	return 0;
}