#include<stdio.h>
struct nod{
	int inf,c;
	nod *urm;
}*l[10000];
FILE *f;
int n,nh,m,r,x[10000],d[10000],t[10000],poz[10000];
void cit(){
	FILE *f;
	nod *p;
	int a,b,c,i;
	f=fopen("dijkstra.in","r");
	fscanf(f,"%d%d%d",&n,&m,&r);
	for(i=1;i<=n;i++)
		l[i]=0;
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d%d",&a,&b,&c);
		p=new nod;
		p->inf=b;
		p->c=c;
		p->urm=l[a];
		l[a]=p;
	}
	fclose(f);
}
void swap(int i,int j){
	int aux;
	poz[x[i]]=j;
	poz[x[j]]=i;
	aux=x[i];
	x[i]=x[j];
	x[j]=aux;
}
void HeapUp(int k){
	if(k<=1)
		return;
	if(d[x[k]]<d[x[k/2]]){
		swap(k,k/2);
		HeapUp(k/2);
	}
}
void HeapDw(int r,int k){
	int st,dr,i;
	if(2*r<=k){
		st=d[x[2*r]];
		if(2*r+1<=k)
			dr=d[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(i,r);
			HeapDw(i,k);
		}
	}
}
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 r){
	int i,k;
	nod *p;
	for(i=1;i<=n;i++){
		x[i]=poz[i]=i;
		t[i]=0;
		d[i]=32000;
	}
	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;
		}
	}
}
void lant(int i){
	if(i!=0){
		lant(t[i]);
		fprintf(f,"%d ",i);
	}
}
void afis(){
	int i;
	f=fopen("dijkstra.out","w");
	for(i=1;i<=n;i++)
		if(i!=r){
			fprintf(f,"%d...%d  ",r,i);
			if(d[i]!=32000){
				fprintf(f,"%d  ( ",d[i]);
				lant(i);
				fprintf(f,")");
			}else
				fprintf(f,"nu exista lant");
			fprintf(f,"\n");
		}
	fclose(f);
}
int main(){
	cit();
	dijkstra(r);
	afis();
	return 0;
}