#include<stdio.h>
#define inf 1000000

struct nod {int v,c;
			nod * next;
		   } * v[50001];
int n,m,d[50001],s[50001],min,poz,t[50001];

void citire()
{   int i,x,y,c;
    nod *p;
	freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{	scanf("%d%d%d",&x,&y,&c);
		p=new nod;
		p->v=y;
		p->c=c;
		p->next=v[x];
		v[x]=p;
	}
	fclose(stdin);
}

void dijkstra(int nd)
{   int i,j;
    nod *p;
	for(i=1;i<=n;i++)
		d[i]=inf;
	d[nd]=0;
	p=v[nd];
	s[nd]=1;
	while(p!=NULL)
	{   d[p->v]=p->c;
        t[p->v]=nd;
		p=p->next;
	}
	for(i=1;i<=n;i++)
	{	min=inf;
	    for(j=1;j<=n;j++)
			if(min>d[j]&&s[j]==0) { min=d[j];
						            poz=j;
						          }
		s[poz]=1;
		p=v[poz];
		while(p!=NULL)
		{	if(d[p->v]>d[poz]+p->c)
			{	d[p->v]=d[poz]+p->c;
				t[p->v]=poz;
			}
			p=p->next;
		}
	}
}
	

int main()
{   int i;
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	for(i=2;i<=n;i++)
		if(d[i]!=inf) printf("%d ",d[i]);
			else printf("0 ");
    fclose(stdout);
	return 0;
}