#include<stdio.h>
FILE *f,*g;
long t[4][300000],fin[50500],c[50500],nr,x,y,z,ok,k,st[400000],dist[50500],p,i,min,inf,nod,m,n,u,pr;
int viz[50500];
int main()
{ f=fopen("dijkstra.in","r"); g=fopen("dijkstra.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  for(i=1;i<=m;i++) 
    {  fscanf(f,"%ld%ld%ld",&x,&y,&z);
       if(c[x]==0) { nr++; c[x]=nr; t[1][nr]=y; t[3][nr]=z; fin[x]=nr; }
	   else { nr++; t[2][fin[x]]=nr; t[1][nr]=y; t[3][nr]=z; fin[x]=nr; }
	}
  ok=1; st[1]=1; viz[1]=1; inf=1000000000; nr=1; pr=u=1;
  while(ok)
   { min=inf; nod=0;
	 for(i=pr;i<=u;i++) 
	  { p=c[st[i]];
	    while(p)
		 { if(!viz[t[1][p]]&&dist[st[i]]+t[3][p]<min) { min=dist[st[i]]+t[3][p]; nod=t[1][p]; }
		   p=t[2][p];
		 }
	  }
		viz[nod]=1; u++; if(u>2) pr++; st[u]=nod; nr++; dist[nod]=min; if(nr==n) ok=0;
   }
  for(i=2;i<=n;i++) fprintf(g,"%ld ",dist[i]);
  fclose(g);
  return 0;
}