//Dijkstra Cu heapuri var 2
#include <cstdio>
const int nmax=50001;
const int Inf=1<<30;
struct nod{int info,cost;
           nod *leg;};
nod *st[nmax];
int d[nmax],h[nmax],p[nmax],n,m,nr;
void add(int where,int what,int cst){
     nod *q=new nod;
     q->info=what;
     q->cost=cst;
     q->leg=st[where];
     st[where]=q;
     }
void citeste(){
     int k,x,y,z;
     freopen("dijkstra.in","r",stdin);
     scanf("%d %d",&n,&m);
     for (k=1;k<=n;k++) st[k]=NULL;
     for (k=1;k<=m;k++) {scanf("%d %d %d",&x,&y,&z);
                         add(x,y,z);}
     }
void Sift(int k){
     int aux,Son,kk;
     if (k<<1<=nr) {Son=k<<1;
                   if (k<<1<nr && d[h[Son]]>d[h[Son+1]]) Son++;
                   if (d[h[Son]]>=d[h[k]]) Son=0;}
           else Son=0;
     kk=k;
     while (Son) {p[h[kk]]=Son;p[h[Son]]=kk;
                  aux=h[kk];h[kk]=h[Son];h[Son]=aux;
                  kk=Son;
                  if (kk<<1<=nr) {Son=kk<<1;
                                if (kk<<1<nr && d[h[Son]]>d[h[Son+1]] ) Son++;
                                if (d[h[Son]]>=d[h[kk]]) Son=0;}
                         else Son=0;
                  }
     } 
void Percolate(int k){
     int key=h[k],kk=k;
     while (kk>1 && d[key]<d[h[kk>>1]]) {p[h[kk>>1]]=kk;
                                      h[kk]=h[kk>>1];
                                      kk=kk>>1;}
     h[kk]=key;
     p[key]=kk;
     }
void Dijkstra(){
     int i,min;
     for (i=1;i<=n;i++) {p[i]=-1;
                         d[i]=Inf;}
     nr=1;h[nr]=1;d[1]=0;
     while (nr>0){
           min=h[1];
           h[1]=h[nr];
           p[min]=1;
           Sift(1);
           nr--;
           for (nod *q=st[min];q!=NULL;q=q->leg)
            if (d[q->info]>d[min]+q->cost)
              {d[q->info]=d[min]+q->cost;
               if (p[q->info]!=-1) Percolate(p[q->info]);
                     else {h[++nr]=q->info;
                           p[q->info]=nr;
                           Percolate(nr);}}
               }
     
     }
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;
    }