#include<stdio.h>
struct point
{
	int x,c;
	point *y;
}*g[10001],*q;
int m,n,i,j,k,h[50001],p[50001],d[50001],x,c,y,nod;
inline void intro(int x, int y, int c)
{
	point *q=new point;
	q->x=y;
	q->c=c;
	q->y=g[x];
	g[x]=q;
}
inline void swap(int i,int j)
{
	int x;
	x=h[i];
	h[i]=h[j];
	h[j]=x;
	x=p[h[i]];
	p[h[i]]=p[h[j]];
	p[h[j]]=x;
}
inline void heapup(int i)
{
	if(d[h[i/2]]<=d[h[i]])return;
	swap(i/2,i);
	heapup(i/2);
}
inline void heapdown(int i)
{
	int st,dr;
	if(i*2>m) return;
	st=d[h[i*2]];
	if(i*2+1<=m)dr=d[h[i*2+1]];else dr=st+1;
	if(st<dr) 
	{
		swap(i,2*i);
		heapdown(i*2);
	}
	else
	{
		swap(i,2*i+1);
		heapdown(2*i+1);
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		intro(x,y,c);
	}
	m=n;
	for(i=1;i<=n;i++)h[i]=i,p[i]=i,d[i]=2000000000;
	d[1]=0;
	d[0]=-1;
	for(i=0;i<n;i++)
	{
		nod=h[1];
		swap(1,m);
		m--;
		heapdown(1);
		for(q=g[nod];q!=NULL;q=q->y)
			if(d[q->x]>d[nod]+q->c)
			{
				d[q->x]=d[nod]+q->c;
				heapup(p[q->x]);
			}
	}
	for(i=2;i<=n;i++)if(d[i]==2000000000)printf("0 ");else printf("%d ",d[i]);
	return 0;
}