#include<stdio.h>
FILE *f,*g;
long t[4][250500],c[50500],i,n,m,st[100000],dist[50500],y,z,nr,p,u,q,viz[50500],x,fin[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; }
   }
  for(i=1;i<=n;i++)
	  dist[i]=1<<30;
  p=u=1; st[1]=1; dist[1]=0;
  while(p<=u)
   { q=c[st[p]]; 
     viz[st[p]]=0;
     while(q!=0) 
	  { if(dist[t[1][q]]>dist[st[p]]+t[3][q]) 
	     { dist[t[1][q]]=dist[st[p]]+t[3][q]; 
	         if(!viz[t[1][q])
			 {
				 viz[t[1][q]]=1;u++; st[u]=t[1][q]; 
			 }
	     }
	    q=t[2][q];
	  }
	 p++;
   }
  for(i=2;i<=n;i++) fprintf(g,"%ld ",dist[i]);
  fclose(g);
  return 0;
}