#include <stdio.h>
#define mx 50010
struct nod
{
	long nr,r;
	nod *ua;
} *l[mx], *p;
struct loch
{
	long d,p;
} dv[mx];
long dimh;
long hp[mx];

void clad(int t, int f, int d)
{
	nod *p;
	p=new nod;
	p->nr=f;
	p->r=d;
	p->ua=l[t];
	l[t]=p;
}

void swap(long i, long j)
{
	long aux=hp[i];
	hp[i]=hp[j];
	hp[j]=aux;
	dv[hp[j]].p=j;
	dv[hp[i]].p=i;
}

void heapup(long i)
{
	if (i>1)
		if (dv[hp[i/2]].d>dv[hp[i]].d)
		{
			swap(i,i/2);
			heapup(i/2);
		}
}

void heapdown(long i)
{
	if (i<<1<=dimh)
	{
		long f=i<<1;
		if (f+1<=dimh && dv[hp[f+1]].d<dv[hp[f]].d)
			f++;
		if (dv[hp[i]].d>dv[hp[f]].d)
		{
			swap(i,f);
			heapdown(f);
		}
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	long n,m,t,d,f;
	scanf("%ld %ld",&n,&m);
	for (int i=1; i<=m; i++)
	{
		scanf("%ld %ld %ld",&t,&f,&d);
		clad(t,f,d);
	}
	for (int i=1; i<=n; i++)
		dv[i].d=1<<30;
	p=l[1];
	dimh=0;
	while (p)
	{
		dimh++;
		dv[p->nr].d=p->r;
		dv[p->nr].p=dimh;
		hp[dimh]=p->nr;
		heapup(dimh);
		p=p->ua;
	}
	long min=1;
	for (int g=1; g<n, min; g++)
	{
		min=hp[1];
		p=l[min];
		long cn=dv[min].d;
		hp[1]=0;
		while (p)
		{
			nod *u;
			u=p->ua;
			long lc=p->nr,ds=p->r;
			if (dv[lc].d>cn+ds)
			{
				dv[lc].d=cn+ds;
				if (dv[lc].p==0)
				{
					dimh++;
					hp[dimh]=lc;
					dv[lc].p=dimh;
				}
				heapup(dv[lc].p);
			}
			delete p;
			p=u;
		}
		hp[1]=hp[dimh];
		dv[hp[1]].p=1;
		dimh--;
		heapdown(1);
	}
	for (int i=2; i<=n; i++)
		if (dv[i].d!=1<<30)
			printf("%ld ",dv[i].d);
		else printf("%ld ",0);
	fclose(stdin);
	fclose(stdout);
	return 0;
}