#include <stdio.h>
#include <stdlib.h>

#define NX 50010
#define INF 0x3f3f3f3f

struct ent {
	int v, w;
	struct ent *next;
};

typedef struct ent ent;

ent G[ NX ], *L[ NX ];
int V, E, hsz;
int h[ NX ], p[ NX ], dist[ NX ];

inline void add( int u, int v, int w ) {
	L[u]->v = v, L[u]->w = w;
	L[u] = L[u]->next = (ent *) malloc( sizeof( ent ) );
}

void cit() {
	int i, u, v, w;
	
	scanf( "%d%d", &V, &E );
	
	for( i = 1; i <= V; i++ )
		L[ i ] = &G[ i ];

	for( ; E; E-- ) {
		scanf( "%d%d%d", &u, &v, &w );
		add( u, v, w );
	}
}

// HEAP shit
inline int hless( int u, int v ) {
	return dist[ h[u] ] < dist[ h[v] ];
}

void hswap( int u, int v ) {
	int x = h[u]; h[u] = h[v]; h[v] = x;
	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;
	while( 1 ) {
		v = u, l = u<<1;
		if( l <= hsz && hless( l, v ) ) v = l;
		if( l < hsz && hless( l+1, v ) ) v = l+1;
		if( v == u ) break;
		hswap( u, v ); u = v;
	}
}

int hpop() {
	int x = h[1];

	hswap( 1, hsz-- );
	hsink( 1 );
	return x;
}

void init() {
	int i;
	
	for( i = 1; i <= V; i++ )
		dist[ h[i] = p[i] = i ] = INF;
	dist[ 1 ] = 0; hsz = V;
}

inline void relax( int u, int v, int w ) {
	if( dist[ v ] > dist[ u ] + w ) {
		dist[ v ] = dist[ u ] + w;
		hswim( p[v] );
	}
}

void rez() {
	int u;
	ent *e;
	
	init();

	// DIJKSTRA shit
	while( hsz ) {
		if( dist[ u = hpop() ] == INF ) break;
		for( e = &G[ u ]; e != L[ u ]; e = e->next )
			relax( u, e->v, e->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;
}