#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("dijkstra.in") ;
ofstream fout ("dijkstra.out") ;

struct nod
{
    nod * next ;
    int info ;
    int cost ;
} ;

int N , M ;
nod * L [50001] ;

void Add ( int , int , int ) ;
void Citire()
{
    int a , b , c  ;
    fin >> N >> M ;
    while ( M >= 1 )
    {
        fin >> a >> b >> c ;
        Add ( a , b , c ) ;
        -- M ;
    }
}

void Add ( int a , int b , int c )
{
    nod * p = new nod ;
    p->info = b ;
    p->cost = c ;
    p->next = L[a] ;
    L[a] = p ;
}

int h[50001] , d[50001] , poz[50001] , k ;
// h = heap care mentine consturile de la nodul 1 la nodul i ;
// d [i] = costul drumului de la nodul 1 la nodul i  .... caut minimizarea acestuia
// poz [i] = pozitia nodului i in HEAP

void swap ( int x , int y ) // interschimb in heap
{
    int aux = h[x] ;
    h[x] = h[y] ;
    h[y] = aux ;
    aux = poz [ h[x] ];
    poz [ h[x] ] = poz [ h[y] ];
    poz [ h[y] ] = aux ;
}

void upheap (int fiu )
{
    int tata ;
    if ( fiu > 1 )
    {
        tata = fiu >> 1;
        if ( d[ h[tata] ] > d[ h[fiu] ] )
        {
            swap (tata, fiu);
            upheap ( fiu ) ;
        }
    }
}

void downheap (int tata )
{
    int fiu;
    if ( tata <= k/2 )
    {
        if ( 2 * tata + 1 <= k )
             if ( d [ h [ 2 * tata ] ] < d [h [ 2 * tata + 1 ] ] )
                         fiu = 2 * tata ;
             else
                         fiu = 2 * tata + 1 ;
        else
             fiu = 2 * tata ;
        if ( d [ h [ tata ] ] > d [h [ fiu ] ] )
                  swap ( tata , fiu ) , downheap ( fiu ) ;

    }
}

const int inf = 1 << 30;

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

    poz[1] = 1;

    h [++k] = 1;

    while ( k )
    {
        int min = h[1];
        swap(1, k);
        -- k;

        downheap (1);

        nod *q = L [min];

        while ( q )
        {
            if ( d[q->info] > d[min] + q->cost )
            {
                d[q->info] = d[min] + q->cost;

                if ( poz[q->info] != -1 )
                    upheap( poz[q->info] );
                else
                {
                    h[++k] = q->info;
                    poz[ h[k] ] = k;
                    upheap( k );
                }
            }
            q = q->next;
        }
    }
}

int main()
{
    Citire () ;
    dijkstra_heap () ;

    int i ;
    for ( i = 2; i <= N; ++i )
        fout << ( d[i] == inf ? 0 : d[i]) << " " ;

    return 0;
}