#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 50010
#define M 250010
#define INF INT_MAX
struct muchie{
       int x,y,c;
};
struct muchie v[M];
int *a[N],*b[N],n,m,d[N];
int h[N],poz[N];
inline int father(int i){
       return i/2;
}
inline int left_son(int i){
       return 2*i;
}
inline int right_son(int i){
       return 2*i+1;
}
void swap(int i,int j){
     int aux;
     aux=h[i];
     h[i]=h[j];
     h[j]=aux;
     poz[h[i]]=i;
     poz[h[j]]=j;
}
void down_heap(int i,int n){
     int maxim=i;
     if (left_son(i)<=n && h[maxim]<h[left_son(i)])
        maxim=left_son(i);
     if (right_son(i)<=n && h[maxim]<h[right_son(i)])
        maxim=right_son(i);
     if (i!=maxim){
       swap(i,maxim);
       down_heap(maxim,n);
     }
}
void up_heap(int i){
     int maxim;
     if (i!=1){
       if (h[i]<h[father(i)]){
         swap(i,father(i));
         up_heap(father(i));
       }
     }
}
void dijkstra(){
     int nh=1,i,x,y;
     h[1]=1;
     poz[1]=1;
     d[1]=0;
     while(nh){
       x=h[1];
       for(i=1;i<=a[x][0];++i){
          y=a[x][i];
          if(d[y]>d[x]+b[x][i]){
            h[++nh]=y;
            poz[y]=nh;
            d[y]=d[x]+b[x][i];
            up_heap(nh);
          }
       }
       swap(1,nh);
       --nh;
       down_heap(1,nh);
     }
}
void scan(){
     int i;
     freopen("dijkstra.in","r",stdin);
     freopen("dijkstra.out","w",stdout);
     scanf("%d%d",&n,&m);
     for(i=0;i<m;++i){
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
        ++d[v[i].x];
     }
     for(i=1;i<=n;++i){
        a[i]=(int*)malloc(d[i]+1);
        b[i]=(int*)malloc(d[i]+1);
        a[i][0]=0;
        b[i][0]=0;
     }
     for(i=0;i<m;++i){
        a[v[i].x][++a[v[i].x][0]]=v[i].y;
        b[v[i].x][++b[v[i].x][0]]=v[i].c;
     }
     for(i=1;i<=n;++i)
        d[i]=INF;
}
void print(){
     int i;
     for (i=2;i<=n;++i)
         printf("%d ",d[i]);
     printf("\n");
}
int main(){
    scan();
    dijkstra();
    print();
}