//Dijkstra cu minheap
#include <cstdio>
typedef struct nod{int info,cost;
                   nod *urm;}NOD;
const int Inf=1<<30;
int n,m,nr,h[50001],d[50001];
NOD *prim[50001],*ult[50001];
void add(int where,int what,int cst){
     NOD *p;
     p=new NOD;
     p->info=what;
     p->cost=cst;
     p->urm=NULL;
     if (prim[where]==NULL) prim[where]=ult[where]=p;
                       else {ult[where]->urm=p;
                             ult[where]=p;}
     }  
void citeste(){
     int i,j,k,cst;
     freopen("dijkstra.in","r",stdin);
     scanf("%d %d",&n,&m);
     for (i=1;i<=n;i++) prim[i]=NULL;
     for (k=1;k<=m;k++) {scanf("%d %d %d",&i,&j,&cst);
                         add(i,j,cst);}
     }
void insert(int key){
     int k;
     h[++nr]=key;
     k=nr;
     while (k>1 && d[key]<d[h[k>>2]]) {h[k]=h[k>>2];
                                       k=k>>2;}
     h[k]=key;
     }
void del(){
     int Son,k=1,aux;
     h[1]=h[nr--];
     if (k<<1<=nr) {Son=k<<1;
                    if (k<<1<nr && d[h[k<<1+1]]<d[h[k<<1]]) Son++;
                    if (d[h[Son]]>=d[h[k]]) Son=0;}
                else Son=0;
     while (Son) {aux=h[k];h[k]=h[Son];h[Son]=aux;
                  k=Son;
                  if (k<<1<=nr) {Son=k<<1;
                                 if (k<<1<nr && d[h[k<<1+1]]<d[h[k<<1]]) Son++;
                                 if (d[h[Son]]>=d[h[k]]) Son=0;}
                            else Son=0;
                  }
     }
void dijkstra(){
     int i,min;
     NOD *p;
     nr=1;h[1]=1;d[1]=0;
     for (i=2;i<=n;i++) d[i]=Inf;
     while (nr>0) {
           min=h[1];
           del();
           p=prim[min];
           while (p!=NULL) {if (d[p->info]>d[min]+p->cost){
                              insert(p->info);
                              d[p->info]=d[min]+p->cost;
                              }
                            p=p->urm;
                            } 
          }
     }
void scrie(){
     int i;
     freopen("dijkstra.out","w",stdout);
     for (i=2;i<=n;i++) if (d[i]<Inf) printf("%d ",d[i]);
                                else printf("%d ",0);
     }
int main(){
    citeste();
    dijkstra();
    scrie();
    return 0;
}