#include <cstdio>
#include <vector>
#include <queue>
#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 ];
queue< int > Q;
int dist[ NX ], col[ NX ], V, E;

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

	scanf( "%d%d", &V, &E );
	w = E / V;

	for( u = 1; u <= V; u++ )
		G[ u ].reserve( w );

	for( ; 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;

	Q.push( 1 );
	while( !Q.empty() ) {
		u = Q.front(); Q.pop();
		col[ u ] = 0;
		for( vector< edge >::iterator e = G[u].begin(); e != G[u].end(); e++ )
			if( dist[ e->v ] > dist[ u ] + e->w ) {
				dist[ e->v ] = dist[ u ] + e->w;
				if( col[ e->v ] == 0 )
					col[ e->v ] = 1, Q.push( e->v );
			}
     }
}

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