//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;
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;
     if (k<<1<=n) {Son=k<<1;
                   if (k<<1<n && d[h[Son]]>d[h[Son+1]]) Son++;
                   if (d[h[Son]]>=d[h[k]]) Son=0;}
           else Son=0;
     while (Son) {p[h[k]]=Son;p[h[Son]]=k;
                  aux=h[k];h[k]=h[Son];h[Son]=aux;
                  k=Son;
                  if (k<<1<=n) {Son=k<<1;
                                if (k<<1<n && d[h[Son]]>d[h[Son+1]] ) Son++;
                                if (d[h[Son]]>=d[h[k]]) Son=0;}
                         else Son=0;
                  }
     } 
void Percolate(int k){
     int key=h[k];
     while (k>1 && d[key]<d[h[k>>1]]) {p[h[k>>1]]=k;
                                      h[k]=h[k>>1];
                                      k=k>>1;}
     h[k]=key;
     p[key]=k;
     }
void Dijkstra(){
     int i,k,min;
     for (i=1;i<=n;i++) {p[i]=-1;
                         d[i]=Inf;}
     k=1;h[k]=1;d[1]=0;
     while (k>0){
           min=h[1];
           h[1]=h[k];
           p[min]=1;
           Sift(1);
           k--;
           for (nod *q=st[min];q;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[++k]=q->info;
                           p[q->info]=k;
                           Percolate(k);}}
               }
     
     }
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;
    }