#include <iostream>
#include <fstream>
#include <vector>

const int MAXN = 5000 ;
const int MAXLEN = 1000000 ;

using namespace std ;

ofstream g ( "dijkstra.out" ) ;

vector < int > legaturi [ MAXN ] ;
vector < int > costuri [ MAXN ] ;
vector < int > drumOptim ;

int copac [ MAXN * 4 ] ;
int nrNoduri , nrMuchii ;

void citireFisier ( )
{
  ifstream f ( "dijkstra.in" ) ;
  f >> nrNoduri ;
  f >> nrMuchii ;
  for ( int i = 0 ; i < nrMuchii ; i ++ )
  {
    int nod , vecin, cost ;
    f >> nod >> vecin >> cost ;
    legaturi [ nod ] . push_back ( vecin ) ;
    costuri [ nod ] . push_back ( cost) ;
  }
  f . close ( ) ;
  return ;
}

void initiereCosturi ( )
{
  for ( int i = 0 ; i <= nrNoduri ; i ++ )
  {
    drumOptim . push_back ( MAXLEN ) ;
  }
  drumOptim [ 1 ] = 0 ;
  return ;
}

bool twoSons ( int Poz )
{
  if ( drumOptim [ copac [ Poz * 2 ] ] < drumOptim [ copac [ Poz * 2 + 1 ] ] )
    return true ;
  return false ;
}

void addTree ( int Val , int Poz , int Left , int Right , int Index )
{
  if ( Left > Poz || Right < Poz )
  {
    return ;
  }
  if ( Left == Right )
  {
    copac [ Index ] = Val ;
    return ;
  }
  int mid = ( Left + Right ) / 2 ;
  addTree ( Val , Poz , Left , mid++ , Index * 2 ) ;
  addTree ( Val , Poz , mid , Right , Index * 2 + 1 ) ;
  if ( twoSons ( Index ) )
    copac [ Index ] = copac [ 2 * Index ] ;
  else 
    copac [ Index ] = copac [ Index * 2 + 1 ] ;
  return ;
}

bool varfCopac ( )
{
  if ( drumOptim [ copac [ 1 ] ] == MAXLEN )
    return false ;
  return true ;
}

void arboreIntervale ( ) 
{
  for ( int i = 1 ; i <= nrNoduri ; i ++ )
  {
    addTree ( i , i , 1 , nrNoduri , 1 ) ;
  }
}

void Dijkstra ( )
{
  if ( varfCopac ( ) )
  {
    int nod = copac [ 1 ] ;
    int len = legaturi [ nod ] . size ( ) ;
    for ( int i = 0 ; i < len ; i ++ )
    {
      if ( drumOptim [ nod ] + costuri [ nod ] [ i ] < drumOptim [ legaturi [ nod ] [ i ] ] )
      {
	drumOptim [ legaturi [ nod ] [ i ] ] = drumOptim [ nod ] + costuri [ nod ] [ i ] ;
	addTree ( legaturi [ nod ] [ i ] , legaturi [ nod ] [ i ] , 1 , nrNoduri , 1 ) ;
      }
    }
    addTree ( 0 , nod , 1 , nrNoduri , 1 ) ;
    Dijkstra ( ) ;
  }
  return ;
}

void scriereFisier ( ) 
{
  for ( int i = 2 ; i <= nrNoduri ; i++ )
  {
    if ( drumOptim [ i ] < MAXLEN )
      g << drumOptim [ i ] << " " ;
    else 
      g << 0 << " " ;
  }
  return ;
}

int main ( ) 
{
  citireFisier ( ) ;
  initiereCosturi ( ) ;
  arboreIntervale ( ) ;
  Dijkstra ( ) ;
  scriereFisier ( ) ;
  return 0 ;
}