#include <iostream>
#include <fstream>
using namespace std;

int const maxn = 50001;
int const maxm = 250001;
int const inf = 1<<29;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


int heap[ maxn ], dim_h, poz[ maxn ];
int viz[ maxn ];
int d[ maxn ];
int N,M;

typedef struct adia
{
    int nod;
    int cost;
    adia* next;
} nod;

nod* lista_a[ maxn ];

void schimba ( int* x , int* y )
{
    int aux;
    aux = *x;
    *x = *y;
    *y = aux;
}
void adauga_in_a( int x, int y , int cost );
void bubble_down( int index );
void bubble_up( int index );
int sterge_din_h () ;
void construieste_h();
void citeste();
void dijkstra();

int main()
{
    citeste();
    construieste_h();
    dijkstra();
    for( int i = 2; i <= N ; i++ )
    {
        if( d[i] == inf )
        g << 0 << " ";
        else
        g << d[i] << " ";
    }
    return 0;
}

void citeste()
{
    f >> N >> M;
    int x,y,z;
    while( f >> x >> y >> z )
    {
        adauga_in_a( x , y, z );
    }
}

void construieste_h()
{

   heap[ ++dim_h ] = 1;
   d [ heap[ 1 ] ] = 0;
   poz[ heap[ 1 ] ] = 1;

   for( int  i = 2 ; i <= N ; i++ )
   {
       d [ i ]  = inf;
       poz[ i ] = -1;
   }

}

void dijkstra()
{
    int aux;
    nod* n_aux;
    while( dim_h )
    {
        aux = sterge_din_h();
        n_aux = lista_a[ aux ];
        while( n_aux )
        {
            if( d[ n_aux->nod ] > d[ aux ] + n_aux->cost )
            {
                d[ n_aux->nod ] = d[ aux ] + n_aux->cost;
                if ( poz[ n_aux->nod] != -1 )
                    bubble_up( poz[ n_aux->nod] );
                else
                {
                    heap[++dim_h] = n_aux->nod;
                    poz[ heap[dim_h] ] = dim_h;
                    bubble_up( dim_h );
                }
            }
            n_aux = n_aux ->next;
        }
    }
}

void adauga_in_a( int x , int y , int costm )
{
    nod* aux =  new nod;
    aux->cost = costm;
    aux->nod = y;
    aux->next = lista_a[ x ];
    lista_a[ x ] = aux;
}

int sterge_din_h()
{
   int sters = 0;
   sters = heap[1];
   schimba ( &heap[1] , &heap[ dim_h ] );
   poz[ heap[ 1 ] ] = 1;
   dim_h--;
   bubble_down(1);
   return sters;
}

void bubble_up( int index )
{
    int ia;

    while( 1 )
    {
        ia = index/2;
        if( ia == 0 )
            break;
        else
        {
            if( d [ heap[ ia ] ] > d [ heap[ index ] ])
            {
               schimba( &heap[ia] , &heap[ index ]);
               poz [ heap[ ia ] ] = index;
               poz [ heap[ index ] ] = ia;
            }
            else break;
        }
    }
}

void bubble_down( int index )
{
    int ia;
    int i1,i2;
    while( 1 )
    {
        i1 = index*2;
        i2 = index*2 + 1;

        if( i1 > dim_h )
            break;
        else if ( i2 > dim_h )
        {
            if(d[ heap[ index ] ]  > d[ heap[i1 ] ] )
            {
               schimba( &heap[index] , &heap[ i1 ]);
               poz [ heap[ index ] ] = i1;
               poz [ heap[ i1 ] ]  = index;
            }

            else break;
        }

        else
        {
            if ( d[ heap [ i1 ] ] < d[ heap [ i2 ] ])
                ia = i1;
            else ia = i2;

            if( d[ heap[ ia ] ] < d [ heap[ index ] ] )
            {
                schimba ( &heap[ ia ] , &heap[ index ] );
                poz[ heap[ ia ] ] = index;
                poz[ heap[ index ] ] = ia;
                index = ia;
            }
            else break;
        }
    }
}