#include<stdio.h>
#define  nmax 50001
#define infinit 2000000000
struct elem{
long v;int cost;
elem* urm;}*a[nmax];
char viz[nmax];long n, d[nmax];
void read()
{
long m,i,x,y,c;
FILE *f=fopen("dijkstra.in","r");
fscanf(f,"%ld%ld",&n,&m);
for(i=0;i<m;i++)
{
	fscanf(f,"%ld %ld %ld",&x,&y,&c);
	elem *p=new elem;
	p->v=y;p->cost=c;
	p->urm=a[x];a[x]=p;
}
fclose(f);
}
void init()
{
long i;
d[1]=0;
for(i=2;i<=n;i++)d[i]=infinit;
}
void bell()
{
struct que{
	long v;int cost;
	que *urm;
} *p,*u,*q;
elem *pl;
long x;
p=new que;
p->v=1;viz[1]=1;
u=p;u->urm=NULL;
while(p)
{
	x=p->v;viz[x]=0;
	for(pl=a[x];pl;pl=pl->urm)
		if(d[pl->v]>d[x]+pl->cost)
		{
		 d[pl->v]=d[x]+pl->cost;
		 if(!viz[pl->v])viz[pl->v]=1;
		 q=new que;
		 q->v=pl->v;u->urm=q;u=q;
		 u->urm=NULL;
		 }
	q=p;p=p->urm;delete q;
}
}
void print()
{
FILE *g=fopen("dijkstra.out","w");
long i;
for(i=2;i<=n;i++)
	if(d[i]==infinit)
		fprintf(g,"0 ");
	else
		fprintf(g,"%ld ",d[i]);
fprintf(g,"\n");
fclose(g);
}

int  main()
{
read();
init();
bell();
print();
return 0;
}