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

using namespace std;

#define NX 50010
#define INF 0x3f3f3f3f

struct edge {
	int u, v, w;
	edge( int a, int b, int c ) : u(a), 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 ) {
		swap( h[u], h[v] );
		swap( p[ h[u] ], p[ h[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;
     }

	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( u, v, w ) );
     }
}

void relax( const edge e ) {
	int tmp = dist[ e.u ] + e.w;
	if( dist[ e.v ] > tmp ) {
		dist[ e.v ] = tmp; H.upd( e.v );
     }
}

void rez() {
	int i, u;
	
	for( i = 1; i <= V; i++ ) {
		dist[ i ] = INF; H.add( i );
     }
	dist[ 1 ] = 0; H.upd( 1 );

	for( i = 1; i <= V; i++ ) {
		u = H.pop();
		if( dist[ u ] >= INF ) break;
		for_each( G[u].begin(), G[u].end(), relax );
	}
}

void scr() {
	int i;
	for( i = 2; i <= V; i++ )
		printf( "%d ", dist[ i ] );
}

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

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

	return 0;
}