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

using namespace std;

#define NX 50010
#define INF 0x3f3f3f3f

#define tr(X,it) \
	for( vector< edge >::iterator it = X.begin(); it != X.end(); it++ )

struct edge {
	int v, w;
	edge( int x = 0, int y = 0 ) : v(x), w(y) {}
};

vector< edge > G[ NX ];

int N, M;
int pos[ NX ], dist[ NX ];

struct Heap {
	int sz, h[ NX ];

	void init() {
		int i;

		sz = N;
		for( i = 1; i <= sz; i++ )
			h[i] = pos[i] = i;
	}

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

	inline void hswap( int u, int v ) {
		swap( h[u], h[v] );
		pos[ h[u] ] = u, pos[ h[v] ] = v;
	}

	void swim( int u ) {
		for( ; u > 1 && hless( u, u>>1 ); u>>=1 )
			hswap( u, u>>1 );
	}

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

	void upd( int x, int y ) {
		dist[ x ] = y;
		swim( pos[x] );
	}

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

Heap H;

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

int get() {
	int x = 0;

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

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

void cit() {
	int u, v, w;
	
	N = get();
	M = get();

	w = M/N;
	for( int u = 1; u <= N; u++ )
		G[u].reserve( w );

	while( M-- ) {
		u = get();
		v = get();
		w = get();
		G[u].push_back( edge(v,w) );
	}
}

void rez() {
	int u;

	for( u = 2; u <= N; u++ )
		dist[ u ] = INF;

	H.init();
	
	while( H.sz ) {
		u = H.pop();
		if( dist[ u ] == INF ) break;
		tr( G[u], e )
			if( dist[u] + e->w < dist[ e->v ] )
				H.upd( e->v, dist[u] + e->w );
	}
}

void scr() {
	for( int i = 2; i <= N; 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;
}