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

struct edge {
	int v, w;
};
typedef struct edge edge;

#define INF 0x3f3f3f3f
#define NX 50010

edge *G[ NX ];
int N, M, sz;
int h[NX], p[NX], dist[NX], deg[NX];

#define BSZ (1<<16)
char buf[BSZ]; int bp;

int get() {
	int x = 0;

	while( buf[bp] < '0' || buf[bp] > '9' )
		if( ++bp == BSZ )
			fread( buf, 1, BSZ, stdin ), bp = 0;

	while( buf[bp] >= '0' && buf[bp] <= '9' ) {
		x = x*10 + buf[bp] - '0';
		if( ++bp == BSZ )
			fread( buf, 1, BSZ, stdin ), bp = 0;
	}
	return x;
}

void cit() {
	int i, u, v, w;
	
	buf[ bp = BSZ-1 ] = 0;
	N = get(), M = get();
	while( M-- )
		u = get(), v = get(), w = get(), deg[u]++;

	for( i = 1; i <= N; i++ )
		G[i] = (edge *)malloc( (deg[i] + 1) * sizeof(edge) ),
		deg[i] = 0;

	rewind( stdin );

	buf[ bp = BSZ-1 ] = 0;
	N = get(), M = get();
	while( M-- )
		u = get(), G[u][deg[u]].v = get(), G[u][deg[u]++].w = get();
}

void hswap( int u, int v ) {
	int t = h[u]; h[u] = h[v]; h[v] = t;
	p[h[u]] = u, p[h[v]] = v;
}

void swim( int node ) {
	int u = p[node];
	for( ; u>1 && dist[h[u]] < dist[h[u>>1]]; u >>= 1 )
		hswap( u, u>>1 );
}

int pop() {
	int x = h[1], u = 1, l, v;
	h[1] = h[ sz-- ];
	while( 1 ) {
		l = u<<1, v = u;
		if( l<=sz && dist[ h[l] ] < dist[ h[v] ] ) v = l;
		if( l<sz && dist[ h[l+1] ] < dist[ h[v] ] ) v = l+1;
		if( v==u ) break;
		hswap( u, v ), u = v;
	}
	return x;
}

void rez() {
	int u, v, w, i;
	
	for( i = 1; i <= N; i++ )
		dist[i] = INF,
		h[i] = p[i] = i;

	dist[1] = 0, sz = N;

	while( sz ) {
		u = pop();
		if( dist[u] == INF ) break;
		for( i = 0; i < deg[u]; i++ ) {
			v = G[u][i].v, w = G[u][i].w;
			if( dist[v] > dist[u] + w )
				dist[v] = dist[u] + w, swim(v);
		}
	}
}

void scr() {
	int i;

	for( i = 2; i <= N; i++ )
		printf( "%d ", dist[i] == INF ? 0 : dist[i] );
	printf( "\n" );
}

int main() {
	freopen( "dijkstra.in", "r", stdin );
	freopen( "dijkstra.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}