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

#define in "dijkstra.in"
#define out "dijkstra.out"
#define NMAX 50005
#define INF (1<<30)

typedef struct nod {
	int vf;
	int cost;
	struct nod* next;
} *PNOD, NOD;

PNOD L[NMAX];
int N, M, ultim, f;
int DP[NMAX], Q1[NMAX], Q2[NMAX], SEL[NMAX];

void Add ( int i, int j, int cost )
{
	PNOD p = (PNOD)calloc( 1, sizeof(NOD) );
	p->vf = j;
	p->cost = cost;
	p->next = L[i];
	L[i] = p;
}

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

	int i, j, cost, nod;
	scanf ( "%d%d", &N, &M );
	for ( ; M > 0; --M )
	{
		scanf ( "%d%d%d", &i, &j, &cost );
		Add ( i, j, cost );
		DP[i] = DP[j] = INF;
	}

	Q1[1] = SEL[1] = 1;	
	DP[f=1] = 0;

	while ( f )
	{
		for ( i = 1; i <= f; ++i )
		{
			nod = Q1[i];
			PNOD j;
			for ( j = L[nod]; j; j = j->next )
			{
				if ( DP[j->vf] > DP[nod] + j->cost )
				{
					DP[j->vf] = DP[nod] + j->cost;
					if ( !SEL[j->vf] ) { SEL[j->vf] = 1; Q2[++ultim] = j->vf; }
				}
			}
		}
		f = ultim; ultim = 0;
		memcpy ( Q1, Q2, sizeof(Q2) );
		memset ( SEL, 0, sizeof(SEL) );
	}
		
	for ( i = 2; i <= N; ++i )
		printf ( "%d ", DP[i] == INF ? 0 : DP[i] );
	
	return 0;
}