#include<iostream.h>
#include<fstream.h>
#include<vector>
using namespace std ;
#define MAXN 100000
#define MAXLONG 2000000000

//ifstream f ( "date.in" ) ;
ofstream g ( "dijkstra.out" ) ;

int heap_size , m , n ;
int heap [ MAXN] , sel [ MAXN ] ;

vector < int > vecini[ MAXN ];
vector < int > costuri[ MAXN ];
int distantaOptima [ MAXN ];

void add_heap ( int Nod )
{
	heap [ ++heap_size ] = Nod ;
	Nod = heap_size ;
	while ( distantaOptima [ heap [ Nod ] ] > distantaOptima [ heap [ Nod ] / 2 ] )
	{
		heap [ Nod ] = heap [ Nod ] + heap [ Nod / 2 ] - ( heap [ Nod ] = heap [ Nod / 2 ] ) ;
		Nod = Nod / 2 ;
	}
}
void reconstituireHeap ( int Nod ) 
{
	int Left = 2 * Nod , Right = Left + 1 , Min = Nod ;
	if ( distantaOptima [ heap [ Nod ] ] > distantaOptima [ heap [ Left ] ] && Left <= heap_size )
	{
		Min = Left ;
	}
	if ( Right <= heap_size && distantaOptima [ heap [ Min ] ] > distantaOptima [ heap [ Right ] ] )
	{
		Min = Right ;
	}
	if ( Min != Nod )
	{
		heap [ Min ] = heap [ Min ] + heap [ Nod ] - ( heap [ Nod ] = heap [ Min ] ) ;
		reconstituireHeap ( Min ) ;
	}
	
}
void elimina_varf_heap ( )
{
	heap [ heap_size ] = heap [ heap_size ] + heap [ 1 ] - ( heap [ 1 ] = heap [ heap_size ] ) ;
	heap_size-- ;
	reconstituireHeap ( 1 ) ;
}
void Dijkstra (int i)
{
  int j,k;
  elimina_varf_heap();
  k = vecini[ i ].size( );
  sel[i]=1;
  for ( j = 0 ; j < k ; j++ )
  {
	  if ( distantaOptima [ vecini [ i ] [ j ] ] > distantaOptima [ i ] + costuri [ i ] [ j ] )
	  {
		  distantaOptima [ vecini [ i ] [ j ] ] = distantaOptima [ i ] + costuri [ i ] [ j ] ;
		  add_heap ( vecini [ i ] [ j ] ) ; 
	  }
  }
  
  do {
	if( heap_size == 0)
		return;
	
  
	k = heap[1];
	if( sel[ k ] == 1 ) elimina_varf_heap();
  }
  while( sel[ k ] == 1);
  
  Dijkstra (k);
  
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	cin>>n>>m;
	int i ;
	for( int i = 1; i <= m; ++i)
	{
		int a, b, cost;
		cin>>a>>b>>cost;
		vecini[a].push_back( b);
		costuri[a].push_back( cost );
		
		// if neorientat
		//vecini[ b ].push_back( a); costuri[b].push_back( cost);
	}
	
	//vecini[ a ].size() -> cate element in vector....
	
	add_heap( 1 );
	
	for( int i = 1; i<= n; ++i) distantaOptima[i] = MAXLONG + 1;
	distantaOptima[1] = 0;
	
	Dijkstra (1);
	for (i=2;i<=n;i++)
	{
		if (distantaOptima[i]== MAXLONG + 1)
		{
		  distantaOptima[i] = 0;
		}
		g<<distantaOptima[i]<<" ";
	}
//	f.close ( ) ;
	g.close ( ) ;
	return 0;
}