#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 ( vector <int> :: iterator it = G[x].begin() , it2 = C[x].begin() ; it < G[x].end() ; ++it , ++it2 ) //parcurgem vecinii lui x
         if ( d[*it] > val + *it2  )  //daca muchia respectiva imbunatateste nodul curent
            d[*it] = val + *it2 , T.insert ( make_pair ( d[*it] , *it ) ) ; //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 )
        g << d[i] << " " ;

    return 0;
}