#include<fstream.h>
#define INF 2500000000

ofstream g("dijkstra.out");

int a[1000][1000],t[1000],n,m,s[1000],d[1000],x,y,z,j,nod,min,k,poz;

void afis(int i)
{
	if(t[i]!=0)
		{
		afis(t[i]);
		g<<i<<" ";
		}
	else
		g<<i<<" ";

}

void main()
{
	ifstream f("dijkstra.in");

	int i;

	f>>n>>m;
	nod=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				a[i][j]=0;
			else
				a[i][j]=INF;

	for(i=1;i<=m;i++)
		{
			f>>x>>y>>z;
			a[x][y]=z;
			a[y][x]=z;
		}

	s[nod]=1;
	for(i=1;i<=n;i++)
	{
		d[i]=a[nod][i];
		if(i!=nod&&d[i]<INF)
			t[i]=nod;
	}

	for(j=1;j<n;j++)
		{
		min=INF;
		for(k=1;k<=n;k++)
			if(s[k]==0&&d[k]<min)
				{
				min=d[k];
				poz=k;
				}
		s[poz]=1;
		for(k=1;k<=n;k++)
			if(s[k]==0&&d[poz]+a[poz][k]<d[k])
					{
					d[k]=d[poz]+a[poz][k];
					t[k]=poz;
					}
		}
	for(j=1;j<=n;j++)
		if(j!=nod)
			{
			g<<"costul de la "<<nod<<" nod la "<<j<<" este "<<d[j]<<endl;
			g<<"drum minim: "<<endl;
			afis(j);
			g<<endl<<endl;
			}
}