#include<fstream>
#include<iostream>
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
int a[5000][5000], d[50000], t[50000],s[50000];
long long nr,m,n;
void dijkstra ( int x )
{
	int mi,ma=32000,y=0,i,j;
	s[x]=1;
	for (  i=1; i<=n; i++ )
	{
		d[i]=a[x][i];
		if ( i!=x && d[i]<ma )
			t[i]=x;
	}
	for ( i=1; i<n; i++ )
	{
		mi=ma;
		for ( j=i; j<=n; j++ )
			if ( s[j]==0 && d[j]<mi  )
			{
				mi=d[j];
				y=j;
				s[y]=1;
			}
		for ( j=1; j<=n; j++ )
			if ( s[j]==0 && d[j]>(d[y]+a[y][j]) )
			{
				d[j]=d[y]+a[y][j];
				t[j]=y;
			}
	}
}

int main ()
{
	f>>n>>m;
	int nr1,nr2,nr3,ant;
	long long i,j;
	for ( i=1; i<=m; i++ )
	{
		f>>nr1>>nr2>>nr3;
		a[nr1][nr2]=nr3; 
		a[nr2][nr1]=nr3;
	}
	for ( i=1; i<=n; i++ )
		for ( j=1; j<=n; j++ )
			if ( a[i][j]==0 )
				a[i][j]=32000;
	dijkstra(1);
	for ( i=2; i<=n; i++ )
	{
		j=i; nr=0;
		ant=i;
		while ( j )
		{
			if ( a[ant][j]!=32000 ) nr=nr+a[ant][j];
			ant=j;
			j=t[j];
			
		}
		g<<nr<<" ";
	}
	for ( i=1; i<=n; i++ )
		cout<<t[i]<<" ";
}