#include<stdio.h>
#include<string.h>
FILE *f,*g;
long t[4][250500],c[50500],i,n,m,st[500000],dist[50500],y,z,nr,p,u,q,viz[50500],x,fin[50500],inf; 
char cr;
int main()
{ f=fopen("dijkstra.in","r"); g=fopen("dijkstra.out","w");
  fscanf(f,"%ld%ld",&n,&m); fscanf(f,"%c",&cr);
  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; }
   }
  p=u=1; st[1]=1; dist[1]=0; inf=1000000000; for(i=2;i<=n;i++) dist[i]=inf;
  while(p<=u)
   { q=c[st[p]]; 
     while(q!=0) 
	  { if(dist[t[1][q]]>dist[st[p]]+t[3][q]) { dist[t[1][q]]=dist[st[p]]+t[3][q]; 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;
}