#include <fstream.h>
#include <limits.h>
#include <conio.h>
#define NM 100
#define INF (INT_MAX-10)/2

int c[NM][NM],d[NM],s[NM],prec[NM],n,m,start=1;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

void build()
{
int j,i,x,y,cost;
in>>n>>m;
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	 c[i][j]=INF;
for(i=1;i<=n;i++)
	c[i][i]=0;
for(i=1;i<=m;i++)
		{in>>x>>y>>cost;
		 c[x][y]=cost;}
in>>start;

}

void init()
{
int i;
s[start]=1;
for(i=1;i<=n;i++)
	{d[i]=c[start][i];
	 if(d[i]<INF&&i!=start)
		 prec[i]=start;
	 }
}

int min()
{
int m=INF*2,i,k;
for(i=1;i<=n;i++)
 if(!s[i]&&d[i]<m){m=d[i];
									 k=i;
									 }
 return k;
}
void dijkstra()
{
int k,i,dc,nrs=1,gata=0;
do{k=min();
	 if(d[k]==INF||nrs==n)
				gata=1;
	 else{s[k]=1;nrs++;
	 for(i=1;i<=n;i++)
		 if(!s[i]){dc=d[k]+c[k][i];
							 if(dc<d[i]){d[i]=dc;
													 prec[i]=k;
													 }
							 }
		 }

		 }while(!gata);
}
void drum(int x)
 {if(x){drum(prec[x]);
				out<<x<<" ";
				}
 }

int main()
{
int i;
build();
init();
dijkstra();
for(i=1;i<=n;i++)
	out<<d[i]<<" ";
out<<endl;
for(i=1;i<=n;i++)
	if(s[i])
	 {out<<"drumul de la "<<i<<" este: ";
		drum(i);
		out<<endl;
		}
	 else out<<"nu exista drum la nodul "<<i<<endl;
return 0 ;

}