#include<fstream.h>
#include<iostream.h>
int a[100][100], d[100] , s[100], p[100] , n;
int MAX=5000;
ifstream f("dijkstra.in");
void init()
{int i, j;f>>n;
for(i=1;i<=n;++i)
	for(j=1;j<=n;++j) if(i!=j) a[i][j]=MAX;
}
void citire()
{
int x,y, i ;
for(i=1;i<=n;++i)f>>x>>y>>a[x][y];
}
void generare_drum(int x)
{int i, j , min, y; s[x]=1;
for(i=1;i<=n;i++)
  { d[i]=a[x][i];
    if(i!=x&&d[i]<MAX)p[i]=x;}
  for(i=1;i<=n-1;++i)
    {for(j=1,min=MAX;j<=n;++j)
	 if(s[j]==0&&d[j]>d[y]+a[y][j])
	   {d[j]=d[y]+a[y][j]; p[j]=y;}}}
void drum(int i)
{if(p[i]!=0)drum(p[i]);cout<<i<<" ";}
void afisare(int x)
{for(int i=1;i<=n;++i)
	if(i!=x)
		if(p[i]!=0)
		{cout<<"drumul cu costul minim de la nodul "<<x;
		cout<<" la nodul "<<i<<" are costul "<<d[i]<<'\n';
		drum(i); cout<<'\n';}
		  else cout<<" nu exista drum de la "<<x<<"la "<<i<<'\n';
	}
int main()
{int x; cout<<"x=";cin>>x;
init();
citire();
generare_drum(x);
afisare(x);
return 0;
}