#include<stdio.h>
struct nod{long int info;long int dist;nod *next;};
nod *prim[500],*pp;
long int n,m,i,a,b,c,h[500],ph[500],d[500],i8,lh,nv,viz[500],dv,nn,dn,aux;
void pune();
void hd(long int ic);
void hu(long int ic);
void sh(long int i1,long int i2);
int main()
{
	FILE *f,*g;f=fopen("dijkstra.in","r");g=fopen("dijkstra.out","w");
	fscanf(f,"%ld%ld",&n,&m);i8=1000000000;
	for(i=1;i<=m;i++){fscanf(f,"%ld%ld%ld",&a,&b,&c);pune();}
	for(i=1;i<=n;i++){h[i]=i;ph[i]=i;d[i]=i8;}d[1]=0;lh=n;
	while(lh&&d[h[1]]<i8)
	{  nv=h[1];viz[nv]=1;dv=d[nv];h[1]=h[lh];ph[h[1]]=1;lh--;hd(1);
	   pp=prim[nv];
	   while(pp)
	   { nn=pp->info;dn=pp->dist;
	     if(viz[nn])pp=pp->next;
	     else
	     { if(d[nn]>dv+dn)
	       { d[nn]=dv+dn;hu(ph[nn]);}
	       pp=pp->next;
	     }
	   }
	}
	for(i=2;i<=n;i++)
	{ if(d[i]==i8)d[i]=0;
	  fprintf(g,"%ld ",d[i]);
	}
	fprintf(g,"\n");fcloseall();return 0;
}
void pune()
{
	nod *paux;
	paux=new nod;
	paux->info=b;
	paux->dist=c;
	if(!prim[a]){paux->next=0;prim[a]=paux;return;}
	paux->next=prim[a];prim[a]=paux;
}
void hd(long int ic)
{
	long int is,is1;
	is=2*ic;is1=is+1;
	if(is>lh)return;
	if(is<lh)if(d[h[is1]]<d[h[is]])is=is1;
	if(d[h[is]]<d[h[ic]]){sh(is,ic);hd(is);}
}
void hu(long int ic)
{
	long int is;
	is=ic/2;
	if(!is)return;
	if(d[h[is]]>d[h[ic]]){sh(is,ic);hu(is);}
}
void sh(long int i1,long int i2)
{
	aux=h[i1];h[i1]=h[i2];h[i2]=aux;
	ph[h[i1]]=i1;ph[h[i2]]=i2;
}