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

#define BUFFSZ (1<<15)
char buff[ BUFFSZ ], *pp = buff;

int get() {
	int x = 0;

	while( *pp < '0' || *pp > '9' )
		if( !*(++pp) )
			fread( buff, 1, BUFFSZ-1, stdin ), pp = buff;

	while( *pp >= '0' && *pp <= '9' ) {
		x = x * 10 + *pp - '0';
		if( !*(++pp) )
			fread( buff, 1, BUFFSZ-1, stdin ), pp = buff;
	}
	return x;
}

void cit() {
	int u, v, w;
	
	V = get();
	E = get();

	for( ; E; E-- ) {
		u = get();
		v = get();
		w = get();
		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 ] == INF ? 0 : dist[ i ] );
}

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

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

	return 0;
}