#include<stdio.h>
FILE *f,*g;
long d,i,n,m,t[6][500005],nr,z,x,y,o,v,c[50005],s[100000],ss[100000],dist[50005],k;
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])
      { while(t[1][nr]!=0||nr==0) nr++;
	c[x]=nr; t[1][nr]=y; t[2][nr]=0; t[3][nr]=z;
      }
     else
      { v=c[x];
	while(t[2][v]!=0) v=t[2][v];
	o=v; while(t[1][o]!=0) o++;
	t[2][v]=o; t[1][o]=y; t[2][o]=0; t[3][o]=z;
      }
   }
  d=1; s[1]=1; d=1; for(i=2;i<=n;i++) dist[i]=-1;
  while(d!=0)
   { for(i=1;i<=d;i++)
      { v=c[s[i]];
	while(v!=0)
	 { k++; ss[k]=t[1][v];
	   if(dist[t[1][v]]==-1||dist[s[i]]+t[3][v]<dist[t[1][v]]) dist[t[1][v]]=dist[s[i]]+t[3][v];
	   v=t[2][v];
	 }
      }
     for(i=1;i<=k;i++) s[i]=ss[i]; d=k; k=0;
   }
  for(i=2;i<=n;i++) if(dist[i]!=-1) fprintf(g,"%ld ",dist[i]); else fprintf(g,"0 ");
  fclose(g);
  return 0;
}