#include<stdio.h>
struct node{
	int to,w,next;
}a[200010];
int head[200010],d[100010],v[100010]={0};
int cnt=1;
int min(int a,int b,int c){
	if(a<b&&a<c){
		return 1;
	}
	if(b<a&&b<c){
		return 2;
	}
	else{
		return 3;
	}
}
void add(int a1,int b,int c){
	a[cnt].w=c;
	a[cnt].to=b;
	a[cnt].next=head[a1];
	head[a1]=cnt++;
}
struct Node{
	int a,b;
}e[300010];
int top;
void rudui(int x,int y){
	top++;
	e[top].a=x;e[top].b=y;	
}
void shangfu(int k){
	if(k==1){
		return;
	}
	if(k%2==0){
		if(e[k].a<e[k/2].a){
			struct Node t=e[k];
			e[k]=e[k/2];
			e[k/2]=t;
			shangfu(k/2);
		}
	}
	else{
		if(e[k].a<e[(k-1)/2].a){
			struct Node t=e[k];
			e[k]=e[(k-1)/2];
			e[(k-1)/2]=t;
			shangfu((k-1)/2);
		}
	}
	return;
}
void back(){
	e[1].a=e[top].a;
	e[1].b=e[top].b;
	top--;
}
void xiafu(int k){
	if(k*2>top){
		return;
	}
	if(k*2+1>top){
		if(e[k].a<e[k*2].a){
			struct Node t=e[k];
			e[k]=e[k*2];
			e[k*2]=t;
			xiafu(k*2);
			return;
		}
		else{
			return;
		}
	}
	else{
		int a=min(e[k].a,e[k*2].a,e[k*2+1].a);
		if(a==1){
			return;
		}
		if(a==2){
			struct Node t=e[k];
			e[k]=e[k*2];
			e[k*2]=t;
			xiafu(k*2);
			return;
		}
		else{
			struct Node t=e[k];
			e[k]=e[k*2+1];
			e[k*2+1]=t;
			xiafu(k*2+1);
			return;
		}
	}	
}

int main()
{
	int n,m,begin;
	scanf("%d%d%d",&n,&m,&begin);
	top=n;
	for(int i=0;i<m;i++){
		int x1,x2,xx;
		scanf("%d%d%d",&x1,&x2,&xx);
		add(x1,x2,xx);
	}
	for(int i=0;i<=n;i++){
		d[i]=1e9+7;
		e[i].a=d[i];e[i].b=i;
	}
	d[begin]=0;e[1].a=0;e[1].b=begin;
	e[begin].b=1;
	for(int i=0;i<n;i++){
		int k=e[1].b;
		v[k]=1;
		for(int j=head[k];j!=0;j=a[j].next){
			if(d[a[j].to]>a[j].w+d[k]){
				d[a[j].to]=a[j].w+d[k];
				if(v[a[j].to]==0){
					rudui(d[a[j].to],a[j].to);
					shangfu(top);
				}			
			}
		}
		back();
		xiafu(1);
	}
	for(int i=1;i<=n;i++){
		printf("%d ",d[i]);
	}
	return 0;
}