#include <cstdio>
#include <vector>
#define oo ( ( 1<<30) - 1 )
#define NMAX 50001
using namespace std;
FILE*fin=fopen("dijkstra.in","r");
FILE*fout=fopen("dijkstra.out","w");
int n , m ;
vector < pair < unsigned   , unsigned   > > vecini[NMAX] ;
bool InCoada[NMAX];
unsigned d[NMAX];

void citire ( )
{
    fscanf( fin , "%d %d" , &n , &m );
    int   x , y , c ;
    for ( unsigned i = 1 ; i <= m ; ++i )
    {
        fscanf( fin , "%d%d%d" , &x ,&y, &c) ;
        vecini[x].push_back( make_pair( y , c ) ) ;
    }
    fclose( fin ) ;
}

unsigned inserare ( unsigned st , unsigned  dr, unsigned  x , unsigned c[] )
{
    if ( st > dr ) return st ;
    unsigned   m = ( st + dr ) / 2 ;
    if ( d[x] < d[c[m]] ) return inserare( st , m - 1 , x , c ) ;
    if ( d[x] > d[c[m]] ) return inserare( m + 1 , dr , x , c ) ;
    else return m ;
}
void adaug ( unsigned p ,unsigned u , unsigned x  , unsigned c[] )
{
    unsigned poz = inserare( p , u , x , c ) ;
    for ( unsigned i = u + 1 ; i > poz ; --i ) c[i] = c[i - 1 ] ;
    c[poz] = x ;
}

void dijkstra ( unsigned  NodStart )
{
    for ( unsigned i = 1 ; i <= n; ++i ) d[i] = oo ;
    d[NodStart] = 0 ;
    unsigned  c[NMAX] ;
    unsigned  p = 1 , u = 1, i ;
    c[1] = NodStart ;
    InCoada[NodStart] = 1 ;
    unsigned  varf ;
    while ( p <= u )
    {
        varf = c[p++] ;
        InCoada[varf] = 0 ;
        for ( size_t i = 0 ; i < vecini[varf].size() ; ++i )
        {
            if ( d[vecini[varf][i].first] > d[varf] + vecini[varf][i].second )
            {
                d[vecini[varf][i].first] = d[varf] + vecini[varf][i].second ;
                if ( InCoada[vecini[varf][i].first] == 0 )
                {
                    InCoada[vecini[varf][i].first] = 1 ;
                    adaug( p , u , vecini[varf][i].first , c ) ;
                    ++u ;
                }
            }
        }
    }
}

void afiseaza ()
{
    for(unsigned  i = 2; i <= n; i++)
    {
        if(d[i] != oo)
            fprintf(fout , "%d " , d[i]);
        else
            fprintf( fout ,"0 " );
    }
    fclose( fout ) ;
}

int main()
{
    citire() ;
    dijkstra ( 1 ) ;
    afiseaza();
    return 0;
}