#include <bits/stdc++.h>
using namespace std;
int n,m,s,u,v,w,f[10005][10005];
long long dis[10005];
bool b[10005];
int main (){
	cin>>n>>m>>s;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			f[i][j]=(1<<31)-1;
		}
	}
	for (int i=1;i<=m;i++){
		cin>>u>>v>>w;
			f[u][v]=min(w,f[u][v]);
		
	}
	for (int i=1;i<=n;i++){
				dis[i]=f[s][i];
		
	}
	dis[s]=0;
	b[s]=1;
	for (int j=1;j<=n-1;j++){
		long long mmin=(1<<31)-1,k=0;
		for (int i=1;i<=n;i++){
			if (b[i]==0&&dis[i]<mmin){
				mmin=dis[i];
				k=i;
			}
		}
		if (k==0){
			break;
		}
		b[k]=1;
		for (int i=1;i<=n;i++){
			if (dis[k]+f[k][i]<dis[i]){
				dis[i]=dis[k]+f[k][i];
			}
		}
	}
	for (int i=1;i<=n;i++){
	
			cout<<dis[i]<<" ";
		
	}
	return 0;
}