#include <iostream>
#include <fstream>
#include <vector>
#define oo ( ( 1<<31) - 1 )
#define NMAX 50001
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");

int n , m ;
vector < pair < int , int > > vecini[NMAX] ;
bool viz[NMAX];
bool InCoada[NMAX];
int d[NMAX];

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

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 , u , i ;
    p = u = i = 1 ;
    c[p] = NodStart ;
    InCoada[NodStart] = 1 ;
    int varf ;
    while ( p <= u )
    {
        varf = c[p++] ;
        viz[varf] = 1 ;
        InCoada[varf] = 0 ;
        for ( size_t i = 0 ; i < vecini[varf].size() ; ++i )
        {
            int 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 )
                {
                    adaug( p , u , vecin , c ) ;
                    ++u ;
                    InCoada[vecin] = 1 ;
                }
            }
        }
    }
}


int main()
{
    citire() ;
    dijkstra ( 1 ) ;
    for ( int i = 2;  i <= n ; ++i ) fout << d[i] << " " ;
    return 0;
}