#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()
{

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

   heap[ ++dim_h ] = 1;
   poz[ 1 ] = 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] ] = dim_h;
   poz[ heap[dim_h] ] = 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 ] ])
            {

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

void bubble_down( int index )
{
    int fiu;
    fiu = index;

    while( index <= dim_h )
    {
        fiu = index;
        if( (index<<1) <= dim_h)
        {
            fiu = index<<1;
            if( fiu + 1 <= dim_h)
                if( d[ heap[fiu] ] > d[ heap[ fiu + 1] ] )
                    fiu++;
        }
        else return;

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

        else return;


    }
}