/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "dijkstra.in" ;
const char OUT [ ] = "dijkstra.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ofstream cout ( OUT ) ;

const int MAX = 5e4 + 14 ;

vector < pair < int , int > > gr [ MAX ] ;

int dist [ MAX ] ;
bitset < MAX > viz ;

int readInt () {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}

vector < pair < int , int > > heap ;

int main()
{
    freopen ( IN , "r" , stdin ) ;
    int n , m ;
    n = readInt() ;
    m = readInt() ;
    while ( m -- )
    {
        int a , b , c ;
        a =readInt() ;
        b =readInt() ;
        c =readInt() ;
        gr [ a ].pb ( mp ( b , c ) ) ;
    }
    FORN ( i , 1 , n ) {
        dist [ i ] = 1 << 30 ;
    }
    dist [ 1 ] = 0 ;
    heap.pb ( mp ( dist [ 1 ] , 1 ) ) ;
    while ( heap.size ( ) > 0 )
    {
        int node = heap [ 0 ].second ;
        int cost = -heap [ 0 ].first ;
        pop_heap ( heap.begin ( ) , heap.end ( ) ) ;
        heap.pop_back() ;
        if ( cost != dist [ node ] ) {
            continue ;
        }
        if ( viz [ node ] ) continue ;
        viz [ node ] = 1 ;
        for ( auto x : gr [ node ] ) {
            if ( dist [ x.first ] > dist [ node ] + x.second ) {
                dist [ x.first ] = dist [ node ] + x.second ;
                heap.pb ( mp ( -dist [ x.first ] , x.first ) ) ;
                push_heap ( heap.begin() , heap.end() ) ;
            }
        }
    }
    FORN ( i , 2 , n ) {
        if ( dist [ i ] >= 1 << 30 ) dist [ i ] = 0 ;
        cout << dist [ i ] << ' ' ;
    }
    return 0;
}