# include <stdio.h>   
# include <stdlib.h>   
# define nmax 501   
# define inf 2000000000   
struct muchie{
  int x,y,c;
} G[nmax];
long D[nmax];
int N,M;
int main()
{
  int i,x,y,c,ok;
  freopen("dijkstra.in","r",stdin);
  freopen("dijkstra.out","w",stdout);
  scanf("%ld %ld",&N,&M);
  for (i=1;i<=M;++i){
   scanf("%d %d %d",&x,&y,&c);
   G[i].x=x; G[i].y=y; G[i].c=c;
   if (x==1) D[x]=c;
  }
  for (i=2;i<=N;++i)
    D[i]=inf;
  do{
     ok=1;
     for (i=1;i<=M;++i)
       if (D[G[i].y]>D[G[i].x]+G[i].c) { D[G[i].y]=D[G[i].x]+G[i].c; ok=0;}
  }while (!ok);
  for (i=2;i<=N;++i)
     if (D[i]!=inf) printf("%ld ",D[i]);
    else printf("0 ");
  return 0;
 }