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

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

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

PNOD L[NMAX];
int N, M, ultim, ff;
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 )
{
	FILE *f = fopen ( in, "r" );

	int i, j, cost, nod;
	fscanf ( f, "%d %d\n", &N, &M );
		
	char linie[19]; char *p; char sep[] = " \n";
	while ( fgets( linie, 19, f ) )
	{
		p = strtok ( linie, sep );
		i = atoi ( p );
		p = strtok ( 0, sep );
		j = atoi ( p );
		p = strtok ( 0, sep );
		cost = atoi ( p );
		DP[i] = DP[j] = INF;
		Add ( i, j, cost );
	}

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

	while ( ff )
	{
		for ( i = 1; i <= ff; ++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; }
				}
			}
		}
		ff = ultim; ultim = 0;
		memcpy ( Q1, Q2, sizeof(Q1[0])*(ff+1) );
		memset ( SEL, 0, (N+1)*sizeof(SEL[0]) );
	}
	f = fopen ( out, "w" );		
	for ( i = 2; i <= N; ++i )
		fprintf ( f, "%d ", DP[i] == INF ? 0 : DP[i] );
	
	fclose ( f );
	return 0;
}