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

using namespace std;

#define NX 50010
#define INF 0x3f3f3f3f

struct edge {
	int v, w;
	edge( int b, int c ) : v(b), w(c) {}
};

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

struct Heap {
private:
	int h[ NX ], p[ NX ], sz;

	bool hless( int u, int v ) {
		return dist[ h[u] ] < dist[ h[v] ];
     }

	void hswap( int u, int v ) {
		int tmp = h[u]; h[u] = h[v]; h[v] = tmp;
		p[ h[u] ] = u; p[ h[v] ] = v;
     }
	
	void hswim( int u ) {
		for( ; u > 1 && hless( u, u>>1 ); u >>= 1 )
			hswap( u, u>>1 );
     }

	void hsink( int u ) {
		int v, l, r;
		while( 1 ) {
			v = u; l = u<<1; r = l+1;
			if( l <= sz && hless( l, u ) ) v = l;
			if( r <= sz && hless( r, v ) ) v = r;
			if( v == u ) break;
			hswap( u, v ); u = v;
     	}
     }

public:
	void add( int x ) {
		h[ ++sz ] = x; p[ x ] = sz;
     }

	void build() {
		sz = V;
		for( int i = 1; i <= sz; i++ )
			h[i] = p[i] = i;
     }

	int pop() {
		int tmp = h[ 1 ];
		hswap( 1, sz-- );
		hsink( 1 );
     	return tmp;
     }

	void upd( int x ) {
		hswim( p[ x ] );
     }
};

Heap H;

void cit() {
	int u, v, w;
	
	for( scanf( "%d%d", &V, &E ); E; E-- ) {
		scanf( "%d%d%d", &u, &v, &w );
		G[u].push_back( edge( v, w ) );
     }
}

void rez() {
	int i, u;
	
	for( i = 1; i <= V; i++ ) {
		dist[ i ] = INF;
     }
	H.build(); dist[ 1 ] = 0;
	
	for( i = 1; i <= V; i++ ) {
		u = H.pop();
		if( dist[ u ] >= INF ) break;
		for( vector< edge >::iterator x = G[u].begin(); x != G[u].end(); x++ )
			if( dist[ u ] + x->w < dist[ x->v ] ) {
				dist[ x->v ] = dist[ u ] + x->w;
				H.upd( x->v );
               }
	}
}

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;
}