#include<stdio.h>
int x[100000],d[100000],t[100000],n,m,nh,r,poz[100000];
struct nod{
	int inf,c;
	nod *urm;
}*L[100000];
void cit(){
	freopen("dijkstra.in","r",stdin);
	scanf("%d%d%d",&n,&m,&r);
	int k,i,j,c;
	nod *q;
	for(k=1;k<=m;k++){
		scanf("%d%d%d",&i,&j,&c);
		q=new nod;
		q->inf=j;
		q->c=c;
		q->urm=L[i];
		L[i]=q;
	}
	fclose(stdin);
	for(i=1;i<=n;i++){
		d[i]=320000;
		poz[i]=i;
		x[i]=i;
	}
}
void swap(int i,int j){
	int aux;
	aux=x[i];
	x[i]=x[j];
	x[j]=aux;
	aux=poz[x[i]];
	poz[x[i]]=poz[x[j]];
	poz[x[j]]=aux;
}
void heapdw(int r,int k){
	int st,dr,i;
	if(2*r<=k){
		st=x[2*r];
		if(2*r+1<=k)
			dr=x[2*r+1];
		else
			dr=st-1;
		if(st>dr)
			i=2*r;
		else
			i=2*r+1;
		if(d[x[r]]>d[x[i]]){
			swap(r,i);
			heapdw(i,k);
		}
		else
			return;
	}
}
void heapup(int k){
	int i;
	if(k<=1)
		return;
	i=k/2;
	if(d[x[k]]<d[x[i]]){
		swap(k,i);
		heapup(i);
	}
	else
		return;
}
void buildh(int k){
	int i;
	for(i=1;i<=k;i++)
		heapup(i);
}
int scoate_heap(){
	swap(1,nh);
	poz[x[nh]]=0;
	nh--;
	heapdw(1,nh);
	return x[nh+1];
}
void dijkstra(){
	int k;
	nod *p;
	d[r]=0;
	buildh(n);
	nh=n;
	while(nh>0){
		k=scoate_heap();
		p=L[k];
		while(p){
			if(d[p->inf]>d[k]+p->c){
				d[p->inf]=d[k]+p->c;
				t[p->inf]=k;
				heapup(poz[p->inf]);
			}
			p=p->urm;
		}
	}
}
int main(){
	cit();
	dijkstra();
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;i++)
		printf("%d ",d[i]);
	fclose(stdout);
	return 0;
}