//Dijkstra
#include<fstream.h>
#define NMaxVf 50
#define Inf 10000

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

void Initializare();
void Afisare();

int main(){
int i,VfMin,j;
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();
return 0;
}

void Initializare()
{
int i,j,m,x,y;
double c;
ifstream fin("graf.in");
fin>>n>>m>>x0;
for(i=1;i<=n;i++)
 for(j=i+1;j<=n;j++)
 C[j][i]=C[i][j]=Inf;
 for(i=1;i<=m;i++)
 { fin>>x>>y>>c;
 C[x][y]=c;}
 for(i=1;i<=n;i++)
 {d[i]=C[x0][i]; pre[i]=x0;}
 M[x0]=1; pre[x0]=0;
 fin.Close(); }
 
 void Afisare()
 { int i,j,lg,dr[NMaxVf];
 for(i=0;i<=n;i++)
  if(i!=x0)
  { cout<<"Costul drumului de cost minim de la "<<x0<<"la"<<i<<"este"<<d[i]<<endl;
  cout<<"Drumul de cost minim:";
  dr[0]=i; lg=0;
  while(pre[dr[lg]])
  {lg++;
  dr[lg]=pre[dr[lg-1]];}
  for(j=lg;j>=0;j--)
  cout<<" "<<dr[j];
  cout<<endl;
  }
  }