#include<stdio.h>
#include<stdlib.h>
int m,n,i,j,x,y,c,d[50013],h[50013],poz[50013];
struct point
{
	int x,c;
	point *y;
}*g[50013],*p;
inline void swap(int i, int j)
{
	int a;
	a=h[i];h[i]=h[j];h[j]=a;
	a=poz[h[i]];poz[h[i]]=poz[h[j]];poz[h[j]]=a;
}
void hu(int i)
{
	if(i==1)return;
	if(d[h[i/2]]>d[h[i]]){swap(i/2,i);hu(i/2);}
}
void hd(int i)
{
	if(i*2>n)return;
	int st,dr;
	st=d[h[i*2]];
	if(i*2+1>n)dr=st+1;
	else dr=d[h[i*2+1]];
	if(st<dr) { swap(i,i*2);hd(i*2);}
	else { swap(i,i*2+1);hd(i*2+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);
		p=new point;
		p->x=y;
		p->c=c;
		p->y=g[x];
		g[x]=p;
	}
	h[1]=poz[1]=1;d[1]=0;
	for(i=2;i<=n;++i){d[i]=1<<30;h[i]=poz[i]=i;}
	y=n;
	while(n>0)
	{
		x=h[1];
		swap(1,n--);
		hd(1);
		for(p=g[x];p!=NULL;p=p->y)
			if(d[x]+p->c<d[p->x])
			{
				d[p->x]=d[x]+p->c;
				hu(poz[p->x]);
			}
	}
	for(i=2;i<=y;++i)
		if(d[i]==1<<30)printf("0 ");
	else printf("%d ",d[i]);
	return 0;
}