#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

#define NX 50010
#define INF 666666

#define TATA(x) (x>>1)
#define ST(x) (x<<1)
#define DR(x) ((x<<1) + 1)

#define pb push_back
#define tr(X,i) \
	for( vector<ent>::iterator i = X.begin(); i != X.end(); i++ )

struct ent {
	int v, w;
	ent( int x, int y ) : v(x), w(y) {}
};

vector< ent > G[ NX ];
int dist[ NX ], col[ NX ];
int V, E;

struct Heap {
	int sz, h[ NX ], p[ NX ];
	
	void swap( int u, int v ) {
		int tmp;
		tmp = h[u]; h[u] = h[v]; h[v] = tmp;
		tmp = p[u]; p[u] = p[v]; p[v] = tmp;
     }

	void swim( int u ) {
		while( dist[ h[ u ] ] < dist[ h[ TATA(u) ] ] && u > 1 )
			swap( u, TATA( u ) );
	}

	void sink( int u ) {
		int ok = u, l = ST( u ), r = DR( u );
		
		if( l <= sz && dist[ h[l] ] < dist[ h[ok] ] ) ok = l;
		if( r <= sz && dist[ h[r] ] < dist[ h[ok] ] ) ok = r;
		if( ok != u )
			swap( ok, u );
     }

	void add( int x, int val ) {
		dist[ x ] = val;
		h[++sz] = x; p[ x ] = sz;
		swim( sz );
     }

	void dec( int x, int newval ) {
		dist[ x ] = newval;
		swim( p[x] );
	}

	int extract() {
		swap( 1, sz-- );
		sink( 1 );
		return h[ sz + 1 ];
     }
} H;

void cit() {
	int i, u, v, w;

	for( scanf( "%d%d", &V, &E ); E; E-- ) {
		scanf( "%d%d%d", &u, &v, &w );
		G[u].pb( ent( v, w ) );
     }
}

void rez() {
	int i, u, sz;
	
	for( i = 1; i <= V; i++ )
		H.add( i, INF );
     H.dec( 1, 0 );

	for( i = 1; i <= V; i++ ) {
		u = H.extract();
		if( dist[ u ] == INF )
			break;
		col[ u ] = 1;
		tr( G[u], x )
			if( dist[ x->v ] > dist[ u ] + x->w )
				H.dec( x->v, dist[ u ] + x->w );
	}
}

void scr() {
	int i;

	for( i = 2; i <= V; i++ )
		printf( "%d ", dist[ i ] == INF ? 0 : dist[ i ] );
}

int main() {
	freopen( "dijkstra.in", "r", stdin );
	freopen( "dijkstra.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}