/*
 * @ Copyright, 3.05.2010
 * Mihai Tabără
 * 325 CA
 * Lab 8 [ PA ]
 * Time Complexity - O(N * logN)
 * Language used: C
 * Operating System: Ubuntu 9.10
 * Environment: Vim
 */

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

#define in "dijkstra.in"
#define out "dijkstra.out"
#define NMAX 50005
#define MMAX 250005
#define INF (1<<30)
#define DIM 3000000

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

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

PNOD L[NMAX];
int N, M;
int dp[NMAX], h[NMAX], pos[NMAX], dim_heap;
char sel[NMAX];
int minim, ok;

void Add( int i, int j, int c)
{
	PNOD p = (PNOD) calloc(1, sizeof(NOD));
	p->vf = j;
	p->c= c;
	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)
	{
		pos[ h[p] ] = minim;
		pos[ h[minim] ] = p;

		h[minim] ^= h[p];
		h[p] ^= h[minim];
		h[minim] ^= h[p];

		Rebuild (minim);
	}
}

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

		h[p] ^= h[tata(p)];
		h[tata(p)] ^= h[p];
		h[p] ^= h[tata(p)];

		p = tata(p);
	}
}

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

	int i, j, k, poz = 0;
	PNOD p;
	char buf[DIM];

	fread (buf, 1, DIM, stdin);
	#define cit(x)										  \
	{													  \
		x = 0;											  \
		while (buf[poz] < '0')							  \
		{												  \
			++poz;										  \
			if (poz == DIM) {							  \
				fread (buf, 1, DIM, stdin); poz = 0; }	  \
		}												  \
		while (buf[poz] >= '0')							  \
		{												  \
			x = x*10 + buf[poz] - '0';					  \
			if (++poz == DIM) {							  \
					fread (buf, 1, DIM, stdin); poz = 0;} \
		}												  \
	}

	cit (N) cit (M)
	for ( ; M; --M)
	{
		cit (i) cit(j) cit(k)
		Add (i, j, k);
	}

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

	while (dim_heap)
	{
		minim = h[1];

		h[1] ^= h[dim_heap];
		h[dim_heap] ^= h[1];
		h[1] ^= h[dim_heap];

		dim_heap--;

		pos[ h[1] ] = 1;
		Rebuild (1);

		for (p = L[minim]; p; p = p->next)
			if (dp[p->vf] > dp[minim] + p->c)
			{
				dp[p->vf] = dp[minim] + p->c;

				if (pos[p->vf] != -1) Up (pos[p->vf]);
				else
				{
					h[++dim_heap] = p->vf;
					pos[p->vf] = dim_heap;
					Up (dim_heap);
				}
			}
	}

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