#include <fstream>
#include <iostream>
using namespace std;

int a[20][20], n, m, k=1;
int viz[20], d[20], tata[20];
const int infinit = 10000;

void citiregraf()
{
  int i,x, y, j, c;
  ifstream f ("graf.in");
  f>>n>>m;
  for(i=1; i<=m; i++)
   { f>>x>>y>>c;
    a[x][y]=a[y][x]=c;
   }
  for (i=1; i<=n; i++)
    for(j=1; j<=n; j++)
      if(a[i][j]==0) a[i][j]=infinit;
  f.close();
}

void drum(int i)
{
  if(tata[i]!=0)
    {
      drum(tata[i]);
      cout<<","<<i;
    }
  else cout<<i;
}

void alg_dijkstra()
 {
   int pas, min, k, i;
   for(pas=1; pas<=n-1; pas++)
     {
       min=infinit;
       for(i=1; i<=n; i++)
	 if((viz[i]==0) && (d[i]<min))
	   { min=d[i]; k=i; }
       viz[k]=1;
       for(i=1; i<=n; i++)
	 if((viz[i]==0) && (d[k]+a[k][i]<d[i]))
	   { d[i]=d[k]+a[k][i]; tata[i]=k; }
     }
 }

int main()
{ int i, s;
  citiregraf();
  cout<<"dati nodul de start"; cin>>s;

  for(i=1; i<=n; i++)
    {
      viz[i]=0;
      d[i]=a[s][i];
      if(d[i]<infinit)
	tata[i]=s;
      else tata[i]=0;
    }
  viz[s]=1; tata[s]=0; d[s]=0;
  alg_dijkstra();

  for(i=1; i<=n; i++)
    {
      cout<<"drumul minim de la "<<s<<" la "<<i<<" este: ";
      drum(i);
      cout<<endl<<"costul este: "<<d[i]<<endl;
    }

}