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

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

#define st(x) (x<<1)
#define dr(x) ((x<<1)+1)
#define tata(x) (x>>1)

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

PNOD L[NMAX];

int h[NMAX], poz[NMAX], dp[NMAX], N, M, dim_heap;


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

void Rebuild ( int p )
{
	int minim, l, r;
	l = st(p); r = dr(p);
	
	if ( l <= dim_heap && dp[ h[l] ] < dp[ h[p] ] )
		minim = l;
	else minim = p;
	
	if ( r <= dim_heap && dp[ h[r] ] < dp[ h[minim] ] )
		minim = r;
	if ( minim != p )
	{
		poz[ h[p] ] = minim;
		poz[ h[minim] ] = p;

		int aux = h[minim];
		h[minim] = h[p];
		h[p] = aux;
		
		Rebuild ( minim );
	}
}

void Up ( int p )
{
	while ( p > 1 && dp [ h[tata(p)] ] > dp [ h[p] ] )
	{
		poz[ h[p] ] = tata(p);
		poz[ h[ tata(p) ] ] = p;

		int aux = h[p];
		h[p] = h[tata(p)];
		h[tata(p)] = aux;

		p = tata(p);
	}
}		

void Dijkstra()
{
	int i;
	for ( i = 2; i <= N; ++i ) { dp[i] = INF; poz[i] = -1; }
	h[1] = poz[++dim_heap] = 1;

	int aux, minim;
	PNOD p;
	
	while ( dim_heap )
	{
		minim = h[1];
		
		aux = h[1];
		h[1] = h[dim_heap];
		h[dim_heap] = aux;

		dim_heap--;
		poz[ h[1] ] = 1;

		Rebuild ( 1 );

		for ( p = L[minim]; p; p = p->next )
			if ( dp[p->vf] > dp[ minim ] + p->cost )
			{
				dp[p->vf] = dp[ minim ] + p->cost;
				
				if ( poz[p->vf] != -1 ) Up ( poz[p->vf] );
				else
				{
					h[++dim_heap] = p->vf;
					poz[ p->vf ] = dim_heap;
					Up ( dim_heap );
				}
			}
	}
}
		
	
int main ( void )
{

	FILE *f = fopen ( in, "r" );
	int i, j, cost;

	fscanf ( f, "%d %d\n", &N, &M );

	char *p;
	char linie[19]; 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);
		Add ( i, j, cost );
	}
	
	f = fopen ( out, "w" );
	
	Dijkstra();

	for ( i = 2; i <= N; ++i )
	{	
		if ( dp[i] == INF ) fprintf ( f, "0 " );
		else fprintf ( f, "%d ", dp[i] );
	}
	fclose ( f );

	return 0;
}