#include <iostream>
#include <fstream>
#include <vector>
#define oo ( ( 1<<30) - 1 )
#define NMAX 50001
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");
unsigned long  n , m ;
vector < pair < unsigned long  , unsigned long  > > vecini[NMAX] ;
bool InCoada[NMAX];
unsigned long d[NMAX];

void citire ( )
{
    fin >> n >> m ;
    unsigned long  x , y , c ;
    for ( unsigned long  i = 1 ; i <= m ; ++i )
    {
        fin >> x >> y >> c ;
        vecini[x].push_back( make_pair( y , c ) ) ;
    }
}

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

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

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

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