//dijkstra's algorithm for single-source shortest paths
#include <cstdio>
#include <cstdlib>

#define NX 50010
#define INF 666666

#define DBG 0

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

ent *G[ NX ];
int V, E;
int deg[ NX ], col[ NX ], dist[ NX ];

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

	for( scanf( "%d%d", &V, &E ); E; E-- ) {
		scanf( "%d%d%d", &u, &v, &w );
		deg[ u ]++;
     }
	for( i = 1; i <= V; i++ ) {
		G[ i ] = (ent *) malloc( (deg[i] + 1) * sizeof( ent ) );
		deg[ i ] = 0;
     }
	rewind( stdin );
	for( scanf( "%d%d", &V, &E ); E; E-- ) {
		scanf( "%d%d%d", &u, &v, &w );
		G[ u ][ deg[u]++ ] = ent( v, w );
     }
	for( i = 1; i <= V; i++ )
		G[ i ][ deg[i] ].v = -1;
}

int getmin() {
	int i, min = INF, pmin = -1;

	for( i = 1; i <= V; i++ )
		if( col[ i ] == 0 )
			if( min > dist[ i ] )
				min = dist[ i ], pmin = i;
	return pmin;
}

void rez() {
	int i, u, sz;
	
	for( i = 1; i <= V; i++ )
		dist[ i ] = INF;
     dist[ 1 ] = 0; sz = V;

	while( sz ) {
		u = getmin(); sz--;
		#if DBG
		printf( "gasit %d. relxez.. \n" );
		#endif
		col[ u ] = 1;
		for( ent *x = G[u]; x->v != -1; x++ ) {
			#if DBG
			printf( "   vecinul %d cu dist %d... ", x->v, dist[ x->v ] );
			#endif
			if( dist[ x->v ] > dist[u] + x->w ) {
				#if DBG
				printf( "relaxez in %d", dist[u] + x->w );
				#endif
				dist[ x->v ] = dist[u] + x->w;
			}
			#if DBG
			printf( "\n" );
			#endif
          }
     }
}

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