#include<stdio.h>
#define inf 1000000

struct muchie{
              long x,y,c;
              }G[500001];

long d[500001],i,n,m,ok;

int main()
{
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);

 scanf("%ld %ld", &n, &m);

 for(i=1;i<=m;i++)
   {
    scanf("%ld %ld %ld", &G[i].x, &G[i].y, &G[i].c);

    if(G[i].x==1) d[G[i].y]=G[i].c;
   }

 for(i=2;i<=n;i++)
  if(d[i]==0) 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;
}