#include<fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int c[50][50],ant[50],v[50],d[50],s[50],n,k,i,nodmax,j,pas,k,minim,maxim;

void citire()
{f>>n;
 for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	if(i!=j)
		c[i][j]=10000;
 while(f>>i>>j>>k)
  c[i][j]=k;
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   if(c[i][j]!=10000)
	  s[i]++;
   
   maxim=s[1];
    for(i=1;i<=n;i++)
		if(s[i]>maxim)
 			{maxim=s[i];
             nodmax=i;  
			}}

void drum(int i)
{if(ant[i])
   drum(ant[i]);
    g<<i;
     else
     g<<i;}

int main()
{ citire();
   for(i=1;i<=n;i++)
   {v[i]=0;
    d[i]=c[nodmax][i];
	 if(d[i]<10000)
		ant[i]=nodmax;
	   else ant[i]=10000;}
   v[i]=1;
   ant[nodmax]=0;
   
   for(pas=1;pas<n;pas++)
   {minim=10000;
   for(i=1;i<=n;i++)
   if(!v[i] && d[i]<minim)
   {minim=d[i];
    k=i;}
   v[k]=1;
    for(i=1;i<=n;i++)
		if(!v[i] && d[i]>d[k]+c[k][i])
		{d[i]=d[k]+c[k][i];
		 ant[i]=k;}}
   for(i=1;i<=n;i++)
   {g<<"drumul minim de la "<<nodmax<<" la "<<i<<" este "<<d[i]<<" ";
    g<<"trece prin";
	drum(i);
	g<<"\n";}
	 
	 
	return 0;}