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

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

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

PNOD L[NMAX];
int N, M;
int d[NMAX];
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;
}

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

	int i, j, k, tur;
	PNOD p;

	scanf ("%d%d", &N, &M);
	for ( ; M; --M)
	{
		scanf ("%d%d%d", &i, &j, &k);
		Add (i, j, k);
	}

	for (i = 1; i <= N; ++i)
	{
		d[i] = INF;
		sel[i] = 0;
	}
	d[1] = 0;

	for (tur = 1; tur <= N; ++tur)
	{
		minim = INF;
		for (i = 1; i <= N; ++i)
			if ( !sel[i] && minim > d[i])
			{
				minim = d[i];
				ok = i;
			}
		sel[ok] = 1;
		for (p = L[ok]; p; p = p->next)
			if ( d[p->vf] > d[ok] + p->c)
				d[p->vf] = d[ok] + p->c;
	}

	for (i = 2; i <= N; ++i)
		printf ("%d ", d[i]);

	return 0;
}