#include<bits/stdc++.h>
using namespace std;
long long s,n,m,h,dis[114514],fl[114514],u,v,w;
bool fll;
struct ed{
	long long to,from,w;
}a[114514];
void add(int x,int y,int z){
	a[++s].from=x;
	a[s].to=y;
	a[s].w=z;
}
void bf(int x){
	while(fll==0){
		for(int i=1;i<=m;i++){
			if(fl[a[i].from]!=1e9){
				dis[a[i].to]=min(dis[a[i].to],fl[a[i].from]+a[i].w);
			}
		}
		for(int i=1;i<=n;i++){
			if(dis[i]!=fl[i]){
				fl[i]=dis[i];
				fll=1;
			}
		}
		if(fll==0){
			return ;
		}
		fll=0;
	}
}
int main(){
	cin>>n>>m>>h;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=1;i<=n;i++){
		fl[i]=dis[i]=1e18;
	}
	fl[h]=dis[h]=0;
	bf(h);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}