#include <iostream>
#include <fstream>

 using namespace std ;

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

 const int NR = 5005 ;
 const int inf = 20005 ;

 int d [ NR ] , C[ NR ][ NR ] ;
 bool M [ NR ] ;
 int n , m , x0 ;

 void init ( )
 {
     f >> n >> m ;
     x0 = 1 ;
     for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = i + 1 ; j <= n ; ++ j )   C [ i ][ j ] = C [ j ][ i ] = inf ;
    for ( int i = 1 ; i <= m ; ++ i )
    {
        int x , y ;
        f >> x >> y ;
        f >> C [ x ][ y ] ;
    }
    for ( int i = 1 ; i <= n ; ++ i )   d [ i ] = C [ x0 ][ i ] ;
    d [ x0 ] = 0 ;
    M [ x0 ] = true ;
 }

 int main ( )
 {
     init ( ) ;
     for ( int j = 1 ; j < n ; ++ j )
{
    int maxim = inf , best = 0 ;
                    for ( int i = 1 ; i <= n ; ++ i )
                        if ( !M [ i ] && maxim > d [ i ] )
                        {
                            maxim = d [ i ] ;
                            best = i ;
                        }
                    M [ best ] = true ;
                    for ( int i =  1 ; i <= n ; ++ i )
                    {
                        if ( !M [ i ] && d [ i ] > maxim + C [ best ][ i ] )
                            d [ i ] = maxim + C [ best ][ i ] ;
                    }



}

for ( int i = 2 ; i <= n ; ++ i )
    if ( d [ i ] == inf )   g << 0 << " " ;
    else                    g << d [ i ] << " " ;
return 0 ;

 }