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

using namespace std;

#define NX 50010
#define INF 0x3f3f3f3f

struct edge {
	int u, v, w;
	edge( int x, int y, int z ) : u(x), v(y), w(z) {}
};

vector< edge > G[ NX ];
int dist[ NX ], col[ NX ], V, E;

struct relax {
	void operator() ( const edge &e ) {
		if( dist[ e.v ] > dist[ e.u ] + e.w )
			dist[ e.v ] = dist[ e.u ] + e.w;
     }
};

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 rez() {
	int i, u;

	for( i = 1; i <= V; i++ )
		dist[ i ] = INF;
     dist[ 1 ] = 0;
	
	for( i = 1; i <= V; i++ )
		for( u = 1; u <= V; u++ )
			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;
}