#include <fstream>
#include <set>
#include <vector>
#include <iostream>

using namespace std ;

#define infinity 1e9

ifstream f ("dijkstra.in") ;
ofstream g ("dijkstra.out") ;

int N , M , d[50002] ; //vectorul pt drumurile de cost minim
vector <int> G[50002] ; //vectorul de muchii
vector <int> C[50002] ; //vectorul de costuri corespunzatoare celui de muchii
set < pair < int , int > > T ;

void solve()
{
    for ( int i = 2 ; i <= N ; ++i )
        d[i] = infinity ; //initial lungimea drumului de la 1 la i e infinity
    T.insert ( make_pair ( 0 , 1 ) ) ; //adaugam nodul 1 cu cost 0

    while( !T.empty ()  )
        {
        int val , x ; //vom alege muchia de cost minim
        val =  T.begin() -> first ; // costul muchiei
        x = T.begin() -> second ; // nodul pt care parcurgem muchiile
        T.erase ( *T.begin() ) ; //stergem muchia
        for ( int i = 0 ; i < G[x].size() ; ++i ) //parcurgem vecinii lui x
         if( d[ G[x][i] ] > val + C[x][i] )  //daca muchia respectiva imbunatateste nodul curent
            d[ G[x][i] ] = val + C[x][i] , T.insert( make_pair ( d[G[x][i]] , G[x][i] ) ) ;//updatam costul si o introducem
        }

}

int main()
{
    f >> N >> M ;

    for ( int i = 1 ; i <= M ; ++i )
        {
         int x , y , c ;
         f >> x >> y >> c ;
         G[x].push_back ( y ) ; //memoreaza muchia (x,y)
         C[x].push_back ( c ) ; //memoreaza costul muchiei corespunzatoare (x,y)
        }

    solve() ;

    for ( int i = 2 ; i <= N ; ++i )
        if ( d[i] != infinity )
            g << d[i] << " " ;
        else
            g << "0 " ;

    return 0;
}