#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 n , m ;
vector < pair < unsigned , unsigned > > vecini[NMAX] ;
bool viz[NMAX];
bool InCoada[NMAX];
unsigned d[NMAX];

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

int inserare ( unsigned st , unsigned dr, unsigned x , unsigned c[] )
{
    if ( st > dr ) return st ;
    int 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 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 , u , i ;
    p = u = 1 ;
    c[p] = NodStart ;
    unsigned varf ;
    while ( p <= u )
    {
        varf = c[p++] ;
        viz[varf] = 1 ;
        for ( size_t i = 0 ; i < vecini[varf].size() ; ++i )
        {
            unsigned vecin , cost ;
            vecin = vecini[varf][i].first ;
            cost = vecini[varf][i].second ;
            if ( d[vecin] > d[varf] + cost )
            {
                d[vecin] = d[varf] + cost ;
                if ( viz[vecin] == 0 && InCoada[vecin] == 0 )
                {
                    InCoada[vecin] = 1 ;
                    adaug( p , u , vecin , c ) ;
                    ++u ;
                }
            }
        }
    }
}

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

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