// programul afiseaza costul infinit intre x,y in caz ca nu exista drum de la x la y
#include <fstream>
#define NMaxVf 50
#define inf 10000
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");

int n,x0,pre[NMaxVf],M[NMaxVf];
double c[NMaxVf][NMaxVf],d[NMaxVf];

void initializare ()
{
  int i,j,m,x,y;
  double cost;
  f>>n>>m>>x0;
  for (i=1; i<=n; i++)
	for (j=i+1; j<=n; j++)    //j=i+1 pentru a evita cazul i=j si pentru a nu face repetitii inutile (i=x,j=y iar apoi i=y,j=x)
	  c[i][j]=c[j][i]=inf;
  for (i=1; i<=m; i++)
  {
	f>>x>>y>>cost;
	c[x][y]=cost;
  }
  for (i=1; i<=n; i++)
  {
	d[i]=c[x0][i];
	pre[i]=x0;
  }
  M[x0]=1; pre[x0]=0;
  f.close ();
}

void afisare ()
{
  int i,j,lg,drum[NMaxVf];
  for (i=1; i<=n; i++)
	if (i!=x0)
	{
	  g<<"Costul drumului de cost minim de la "<<x0<<" la "<<i<<" este "<<d[i]<<'\n';
	  drum[0]=i; lg=0;
	  while (pre[drum[lg]])
		drum[++lg]=pre[drum[lg-1]];
	  g<<"Drumul de cost minim: ";
	  for (j=lg; j>=0; j--)
		g<<drum[j]<<" ";
	  g<<'\n';
	}
}
  
int main ()
{
  int i,j,VfMin;
  double dMin;
  initializare ();
  for (j=1; j<n; j++)
  {
	dMin=inf;
	for (i=1; i<=n; i++)
	  if (!M[i] && dMin>d[i])
	  {
		dMin=d[i];
		VfMin=i;
	  }
	  M[VfMin]=1;
	  for (i=1; i<=n; i++)
		if (!M[i] && d[i]>dMin+c[VfMin][i])
		{
		  pre[i]=VfMin;
		  d[i]=dMin+c[VfMin][i];
		}
  }
  afisare ();
  g.close (); return 0;
}