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

#define nmax 50001

using namespace std ;

struct nod
{
    int nod ;
    int distanta ;
}arb[ 3 * nmax ] , asd , infinit;

vector <nod> vecini [ nmax ] ;
int N , M ;
int distanta [ nmax ] , poz [ nmax ] ;
int p , u ;
bool valid [ nmax ] ;


nod minim ( nod a , nod b )
{
    if ( a.distanta < b.distanta ) return a;
        else return b;
}
void update ( int nod0 , int stanga , int dreapta , int a , nod b )
{
    if ( stanga == dreapta )
        arb [ nod0 ] = b ;
        else
        {
            int mid = ( stanga + dreapta  ) / 2 ;
            if ( a <= mid ) update ( 2 * nod0 , stanga , mid , a , b ) ;
                else update ( 2 * nod0 + 1 , mid + 1 , dreapta , a , b ) ;
            arb[ nod0 ] = minim ( arb [ 2 * nod0 ] , arb [ 2 * nod0 + 1 ] ) ;
        }
}

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

    update ( 1 , 1 , N , nod , infinit ) ;


    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  )
            {
                distanta [ vecin ] = distanta [ nod ] + muchie ;

                asd.nod = vecin ;
                asd.distanta = distanta [ vecin ] ;
                update ( 1 , 1 , N , vecin , asd ) ;
            }

    }

    nod = arb [ 1 ].nod ;
    dijkstra ( nod ) ;

}
void build ( int nod , int stanga , int dreapta )
{
    if ( stanga == dreapta )
        arb [ nod ] = infinit ;
        else
            {
                int mid = ( stanga + dreapta ) / 2 ;
                build ( 2 * nod , stanga , mid ) ;
                build ( 2 * nod + 1 , mid + 1 , dreapta ) ;
                arb [ nod ] = minim ( arb [ 2 * nod ] , arb [ 2 * nod + 1 ] ) ;
            }
}
void dist ()
{
    valid [ 1 ] = 1 ;
    distanta [ 1 ] = 0;

    for ( int i = 2 ; i <= N + 4 ; i++ )
    {
        valid [ i ] = 1 ;
        distanta [ i ] = infinit.distanta ;
    }
}

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 ) ;
    }

    infinit.distanta = 1 << 30 ;
    infinit.nod = 0 ;

    dist () ;
    build ( 1 , 1 , N ) ;
    arb [ 1 ].nod = 1 ;
    arb [ 1 ].distanta = infinit.distanta ;
    dijkstra ( 1 ) ;

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


    fclose ( fin ) ;
    fclose ( fout ) ;

    return 0 ;


}