#include <stdio.h>
#include <stdlib.h>
const int N=50002, M=250002, INF=2147000000;
struct per{int x,y,c;}a[M];
struct mc{int y,c;}*v[N];
struct hp{int x,d;}H[N];
int d[N],g[N],p[N],L;

inline void swap(hp &a, hp &b){hp t=a;a=b;b=t;}

void up(int i){
  hp auxh = H[i]; int j;

  while ((i>>1)>0 && H[i>>1].d > auxh.d){
    j=i>>1;p[H[j].x] = i; H[i]=H[j];  i=j;
  }
  p[auxh.x]=i; H[i]=auxh;
}

void down(int i){
  int f;
  while ((i<<1) <= L){
    f=i<<1;
    if ( (f|1)<= L)if ( H[f|1].d < H[f].d ) f|=1;
    if ( H[i].d > H[f].d ){
      swap(H[i],H[f]); p[H[i].x]=i; p[H[f].x]=f; i=f;
    }
    else return;
  }
}

int main(){
  freopen("dijkstra.in","r",stdin); freopen("dijkstra.out","w",stdout);
  int n,m,i,x,val,f;

  scanf("%d %d",&n,&m);
  for (i=1;i<=m;++i)scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c),g[a[i].x]++;

  for (i=1;i<=n;++i)v[i]=(mc*)malloc(g[i]*sizeof(mc)),g[i]=0;
  for (i=1;i<=m;++i){
    v[a[i].x][g[a[i].x]].y = a[i].y;
    v[a[i].x][g[a[i].x]++].c = a[i].c;
  }
  
  L=1; H[1].d=0; H[1].x=1;
  for (i=2;i<=n;++i)d[i]=INF;
  
  while (L){
    //extrage nod varf
    x=H[1].x; val=H[1].d; p[x]=0;
    H[1]=H[L]; L--; down(1);
    //
    for (i=0;i<g[x];++i)
      if ( d[ f=v[x][i].y ] > val + v[x][i].c ){
        d[ f ] = val + v[x][i].c;
        if (p[f]){ H[ p[f] ].d = d[f]; up( p[f] ); }
        else { ++L; p[f]=L; H[L].x=f; H[L].d = d[f]; up(L); }
      }
  }
  
  for (i=2;i<=n;++i)if (d[i]==INF)printf("0 "); else printf("%d ",d[i]);
  
return 0;
}