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

#define NMAX 50001
#define TREE_MAX 1 << 17
#define MMAX 100001
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define MIN( a, b ) ( (a) < (b) ) ? (a) : (b)
#define INFINIT 1000000000


typedef struct cell
{
	int info, cost;
	struct cell * next;
}NOD;

NOD * V[NMAX];
int N, M, TREE[TREE_MAX], D[NMAX], SOL[NMAX], SEL[NMAX], pos;
FILE * fin, * fout;

void init( int nod, int left, int right )
{
	int half;
	if( left == right )
		TREE[nod] = left;
	else
	{
		half = ( left + right ) >> 1;
		init( 2 * nod, left, half );
		init( 2 * nod + 1, half + 1, right );
		TREE[nod] =  D[TREE[2*nod]] < D[TREE[2*nod+1]] ? TREE[2*nod] : TREE[2*nod+1]; 
		
	}
}


void update( int nod, int left, int right )
{
	int half;
	if ( left < right )
	{
		half = ( left + right ) >> 1;
		if( pos <= half ) 
			update( 2 * nod, left, half );
		else
			update( 2 * nod + 1, half + 1, right );
		TREE[nod] =  D[TREE[2*nod]] < D[TREE[2*nod+1]] ? TREE[2*nod] : TREE[2*nod+1];
	}
}

void Dijkstra( int start )
{
	int i, nod;
	NOD * tmp;
	for( i = 1; i <= N; i++ )
		D[i] = INFINIT;
	D[start] = 0;
	init( 1, 1, N );
	while ( D[TREE[1]] != INFINIT )
	{
		nod = TREE[1];
		tmp = V[nod];
		while ( tmp != NULL )
		{
			if ( D[nod] + tmp->cost < D[tmp->info] && !SEL[tmp->info])
			{
				D[tmp->info] = D[nod] + tmp->cost;
				pos = tmp->info;
				update( 1, 1, N );
			}
			tmp = tmp->next;
		}
		SOL[nod] =  D[nod];
		SEL[nod] = 1;
		D[nod] = INFINIT;
		pos = nod;
		update( 1, 1, N );
		
	}
}

inline void push( NOD *& list, int info, int cost )
{
	NOD * q = new NOD;
	q->info = info;
	q->cost = cost;
	q->next = NULL;
	if (!list )
		list = q;
	else
	{
		q->next = list;
		list = q;
	}
}

int main()
{
	int i, x, y, cost;
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d%d", &N, &M );
	for( i = 1; i <= N; i++ )
		V[i] = NULL;
	while( M )
	{
		fscanf( fin, "%d%d%d", &x, &y, &cost );
		push( V[x], y, cost );
		M--;
	}
	Dijkstra( 1 );
	for( i = 2; i <= N; i++ )
		fprintf( fout, "%d ", SOL[i]);
	fprintf( fout, "\n" );
	fclose(fin);
	fclose(fout);
	return 0;
}