#include<fstream.h>
#include<limits.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 fin("dijkstra.in");
ofstream fout("dijkstra.out");

void build()
{
 int i,j,x,y,cost;
 fin>>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++)
 { fin>>x>>y>>cost;
   c[x][y]=cost;
 }
 fin>>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=0;

 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]);
 cout<<x<<" ";
 }
}

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