#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,w,next;
};node bian[500010];
int head[500010];
int dis[500010];
int flag[500010];
int n,m,s,cnt;
void add(int x,int y,int w){
	cnt++;
	bian[cnt].x=x;
	bian[cnt].y=y;
	bian[cnt].w=w;
	bian[cnt].next=head[x];
	head[x]=cnt;
}
void djskl(int x){
	for(int i=1;i<=n;i++)
		dis[i]=0x3f3f3f3f;
	dis[x]=0;
	flag[x]=1;
	for(int k=head[x];k;k=bian[k].next)
		dis[bian[k].y]=bian[k].w;
	for(int i=1;i<=n-1;i++){
		int minn=987654321,t=0;
		for(int j=1;j<=n;j++){
			if(dis[j]<minn&&flag[j]==0){
				minn=dis[j];
				t=j;
			} 
		}
		flag[t]=1;
		for(int k=head[t];k;k=bian[k].next){
			if(bian[k].w+dis[t]<dis[bian[k].y]){
				dis[bian[k].y]=bian[k].w+dis[t];
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	djskl(s);
	return 0;
}