#include <stdio.h>

#define nmax 50005
#define inf ((unsigned int)1<<31)-1
#define pr(x) fprintf (stderr, "%d\n", x)


struct nod
{
	int n, v;
	nod *next;
};

nod *f [nmax];
int n, m, nr_h;
int h [nmax];
int p [nmax];
int d [nmax];



void insert (int n_i, int n_f, int v)
{
	nod *aux;
	aux=new nod;
	aux->n=n_f;
	aux->v=v;
	if (f [n_i] == 0)
		aux->next=NULL;
	else
		aux->next=f [n_i];
	f [n_i]=aux;
}

void scan ()
{
	int i, a, b, c;
	scanf ("%d%d", &n, &m);
	for (i=1; i<=m; ++i)
	{
		scanf ("%d%d%d", &a, &b, &c);
		insert (a, b, c);
	}
}

inline void swap (int p1, int p2)
{
	int aux;
	aux=h [p1];
	h [p1]=h [p2];
	h [p2]=aux;
}

void up (int k)
{
	int t=k>>1;
	if (t >= 1 && d [h [t]] > d [h [k]])
	{
		swap (t, k);
		p [h [t]]=t;
		p [h [k]]=k;
		up (t);
	}
}

void down (int k)
{
	int f=k, min=d [h [k]];
	if (k << 1 <= nr_h && d [h [k<<1]] < min)
	{
		f=k<<1;
		min=d [h [f]];
	}
	if (((k << 1)|1) <= nr_h && d [h [(k<<1)|1]] < min)
	{
		f=(k<<1)|1;
		min=d [h [f]];
	}
	if (f == k)
		return ;
	swap (f, k);
	p [h [f]]=f;
	p [h [k]]=k;
	down (f);
}

void init ()
{
	d [1]=inf;
	nod *i;
	for (i=f [1]; i != NULL; i=i->next)
	{
		h [++nr_h]=i->n;
		p [i->n]=nr_h;
		d [i->n]=i->v;
	}
	int j;
	for (j=nr_h/2; j <= nr_h; ++j)
		down (j);
}

void dijkstra ()
{
	nod *i;
	init ();
	while (nr_h)
	{
			for (i=f [h [1]]; i != NULL; i=i->next)	
				if (d [i->n] > d [h [1]] + i->v)
				{
					d [i->n]=d [h [1]] + i->v;
					up (p [i->n]);
				}
				else
					if (d [i->n] == 0)
					{
						d [i->n]=d [h [1]] + i->v;
						h [++nr_h]=i->n;
						p [i->n]=nr_h;
						up (nr_h);
					}
			h [1]=h [nr_h];
			--nr_h;
			down (1);
	}
}

void print ()
{
	int i;
	for (i=2; i <= n; ++i)
		printf ("%d ", d [i]);
	printf ("\n");
}

int main ()
{
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	scan ();
	dijkstra ();
	print ();
	return 0;
}