#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

int hea[100005],nex[200005],toe[200005],qz[200005];
bool hx[100005];
int di[100005],du[5000005],tn,tt,n,m,s;

void rd(int k){
	du[++tt]=k;
	int l=tt;
	while(l>1){
		int q=(l>>1);
		if(di[du[l]]>=di[du[q]]) l=1;
		else{
			swap(du[l],du[q]);
			l=q;
		}
	}
	return ;
}

int cd(){
	int jg=du[1],l=1;
	du[1]=du[tt--];
	while(l*2<=tt){
		int q=(l<<1);
		if(di[du[q]]>di[du[q+1]]) q++;
		if(di[du[l]]<=di[du[q]]) l=tt;
		else{
			swap(du[l],du[q]);
			l=q;
		}
	}
	return jg;
}
                               
void qxx(int a,int b,int c){
	nex[++tn]=hea[a];
	toe[tn]=b;
	qz[tn]=c;
	hea[a]=tn;
	return ;
}

int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		qxx(a,b,c);
	}
	memset(di,127,sizeof(di));
	di[s]=0;rd(s);
	while(tt>0){
		int k=cd();
		if(!hx[k]){
			hx[k]=1;
			for(int j=hea[k];j;j=nex[j]){
				if(!hx[toe[j]]){
					int l=qz[j]+di[k];
					if(l<di[toe[j]]){
						di[toe[j]]=l;
						rd(toe[j]);
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",di[i]);
	return 0;
}