#include<fstream.h>
#include<stdio.h>
FILE *f,*g;
long 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",f);
int x,y,co;
elem *p;
fscanf(f,"%d%d\n",&n,&m);
for(int i=0;i<m;i++)
	{
	fscanf(f,"%d%d%d\n",&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(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",g);
for(int i=2;i<=n;i++)
	{
	if(d[i]==2000000000)
		fprintf(g,"0 ");
	else
		fprintf(g,"%d ",d[i]);
	}
fclose(g);
}

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