#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 < int , int > > vecini[NMAX] ;
bool InCoada[NMAX];
int d[NMAX];

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

int inserare ( int st , int  dr, int  x , int c[] )
{
    if ( st > dr ) return st ;
    int   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 ( int p ,int u , int x  , int c[] )
{
    int poz = inserare( p , u , x , c ) ;
    for ( int i = u + 1 ; i > poz ; --i ) c[i] = c[i - 1 ] ;
    c[poz] = x ;
}

void dijkstra ( int NodStart )
{
    for ( int i = 1 ; i <= n; ++i ) d[i] = oo ;
    d[NodStart] = 0 ;
    int c[NMAX] ;
    int  p = 1 , u = 1, i ;
    c[1] = NodStart ;
    InCoada[NodStart] = 1 ;
    int  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(int  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;
}