#include<fstream.h>
#include<stdio.h>
//FILE *f,*g;
long int viz[500],n,m,d[500];
struct coada
{
long inf;
coada *urm;
}*c,*ultim;

struct elem
{
long inf;
int cost;
elem *urm;
}*a[500];
void citire()
{
freopen("dijkstra.in","r",stdin);
long int x,y,co;
elem *p;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
	{
	scanf("%d%d%d",&x,&y,&co);
	p=new elem;
	p->inf=y;
	p->cost=co;
	p->urm=a[x];
	a[x]=p;
	}
//fclose(f);
}
void prima()
{
elem *p;
d[1]=0;
for(long int i=2;i<=n;i++)
{
	d[i]=2000000000;
}

}
void implementare()
{
 coada *q,*t;
 elem *p;
 c=new coada;
 c->inf=1;
 c->urm=NULL;
 viz[1]=1;
 ultim=c;
 while(c!=NULL)
 {

	p=a[c->inf];
	while(p!=NULL)
	{
	if(d[p->inf]>d[c->inf]+p->cost)
		{
		d[p->inf]=d[c->inf]+p->cost;
		if(viz[p->inf]==0)
			{
			q=new coada;
			viz[p->inf]=1;
			q->inf=p->inf;
			q->urm=NULL;
			ultim->urm=q;
			ultim=q;
			}
		}
	p=p->urm;
	}
 t=c;
 viz[c->inf]=0;
 c=c->urm;
 delete t;
 }

}
void afisare()
{
freopen("dijkstra.out","w",stdout);
for(long int i=2;i<=n;i++)
	{
	if(d[i]==2000000000)
		printf("0 ");
	else
		printf("%ld ",d[i]);
	}
printf("\n");
}

int main()
{
citire();
prima();
implementare();
afisare();
return 0;
}