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

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

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

void build(){
int i,j,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 minim(){
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;
do{
			k=minim();
			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<<"drum pana la"<<i<<"este: ";
 drum(i);
 out<<endl;
 }
 else
			out<<"Nu exista drum de la nodul "<<i<<endl;
			return 0;
			}