#include <cstdio>
#include <cstdlib>
#include <vector>

#define nmax 50001

using namespace std ;

struct nod
{
    int nod ;
    int distanta ;
}heap[ nmax ];

vector <nod> vecini [ nmax ] ;
int infinit = 1 << 30 ;
int N , M ;
int distanta [ nmax ] , poz [ nmax ] ;
int heap_nr ;
bool valid [ nmax ] ;

void swap ( nod &a , nod &b )
{
    nod aux ;
    aux = a ;
    a = b ;
    b = aux ;
}
void upheap ( int k )
{
    if ( k / 2 >= 1 )
        if ( heap [ k ].distanta < heap [ k / 2 ].distanta  )
            {
                swap ( heap [ k ] , heap [ k / 2 ]  ) ;
                upheap ( k / 2 ) ;
            }
}
void downheap ( int k )
{
    if ( 2 * k <= heap_nr )
    {
        int min = 2 * k  ;
        if ( 2 * k + 1 <= heap_nr && heap [ 2 * k + 1 ].distanta < heap [ 2 * k ].distanta  )
            min = 2 * k + 1 ;
        if ( heap [ min ].distanta < heap [ k ].distanta )
            {
                swap ( heap [ min ] , heap [ k ] ) ;
                downheap( min ) ;
            }
    }
}
void dist ()
{
    distanta [ 1 ] = 0 ;
    valid [ 1 ] = 1 ;
    for ( int i = 2 ; i <= N ; i++ )
    {
        distanta [ i ] = infinit ;
        valid [i] = 1 ;
    }
}

void dijkstra ( int nod )
{
    if ( !valid [ nod ] ) return ;


    swap ( heap [ 1 ] , heap [ heap_nr ] ) ;
    heap_nr-- ;
    downheap ( 1 );

    valid [ nod ] = 0 ;

    for ( int i = 0 ; i < vecini [ nod ].size () ; i++ )
    {
        int vecin = vecini [ nod ][ i ].nod ;
        int muchie = vecini [ nod ][ i ].distanta ;
        int distanta_veche = distanta [ vecin ] ;

        if ( distanta_veche > distanta [ nod ] + muchie && valid [ vecin ]  )
            {
                distanta [ vecin ] = distanta [ nod ] + muchie ;
                heap_nr++ ;
                heap [ heap_nr ].nod = vecin ;
                heap [ heap_nr ].distanta = distanta [ vecin ] ;
                upheap ( heap_nr );

            }
    }
    nod = heap [ 1 ].nod ;
    dijkstra ( nod ) ;

}


int main ()
{
    FILE *fin , *fout ;
    fin = fopen ( "dijkstra.in" , "rt" ) ;
    fout = fopen ( "dijkstra.out" , "wt" ) ;

    fscanf ( fin , "%d %d" , &N , &M ) ;
    for ( int i = 1 ; i <= M ; i++ )
    {
        int a ;
        nod asd ;
        fscanf ( fin , "%d %d %d" , &a , &asd.nod , &asd.distanta ) ;
        vecini [ a ].push_back ( asd ) ;
    }

    dist () ;
    heap_nr++;
    heap [ heap_nr ].nod = 1 ;
    heap [ heap_nr ].distanta = 0 ;
    dijkstra ( 1 ) ;

    for ( int i = 2 ; i <= N ; i++ )
        if ( distanta [ i ] != infinit ) fprintf ( fout , "%d " , distanta [ i ] ) ;
            else fprintf ( fout , "0 " );


    fclose ( fin ) ;
    fclose ( fout ) ;

    return 0 ;


}