#include <stdio.h>
#define DIM 50005
#define INF 100000

struct nod {int x,ct;
			nod *urm;} *lst[DIM];
int c[DIM],h[DIM],poz[DIM];
int n,m,l;

void add (int a,int b,int c)
{
    nod *p=new nod;
    p->x=b;
    p->ct=c;
    p->urm=lst[a];
    lst[a]=p;
}

void read ()
{
    int i,x,y,z;
    scanf ("%d%d",&n,&m);
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d%d",&x,&y,&z);
        add (x,y,z);
    }
}

void init ()
{
    int i;
	poz[++i]=1;
	for (i=2; i<=n; ++i)
		c[i]=INF;
}

void swap (int &a,int &b)
{
	int tmp=a;
	a=b;
	b=tmp;
}

void upheap (int nod)
{
	if (nod<=1) return;
	if (h[nod]>h[nod/2])
		{
		swap(h[nod], h[nod/2]);
		swap(poz[h[nod]], poz[h[nod/2]]);
		upheap(nod/2);
		}
}

void downheap (int nod)
{
	int max=nod;
	if (2*nod<=l)
		{
			max=2*nod;
			if (2*nod+1<=l && c[h[2*nod+1]]<c[h[2*nod]])
				max=2*nod+1;
			if (c[h[max]]>=c[h[max]])
				max=0;
		}
	if (max!=nod)
		{
			swap (poz[h[nod]],poz[h[max]]);
			swap (h[nod],h[max]);
			downheap(max);
		}
}
void solve ()
{
	nod *p;
	int i,min;
	for (h[++l]=1; l; )
	{
		min=h[1];
		h[1]=h[l--];
		poz[h[1]]=1;
		downheap (1);
		for (p=lst[min]; p; p=p->urm)
			if (c[p->x]>c[min]+p->ct)
			{
				c[p->x]=c[min]+p->ct;
				if (poz[p->x])
					upheap (poz[p->x]);
				else
				{
					poz[h[++l]=p->x]=l;
					upheap (l);
				}
			}
	}
}

void print ()
{
	int i;
	for (i=2; i<=n; ++i)
		if (c[i]!=INF)
			printf ("%d ",c[i]);
		else
			printf ("0 ");
}

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