#include<stdio.h>   
struct nod{long int info;long int dist;nod *next;};   
nod *prim[50002],*pp;   
long int n,m,i,a,b,c,h[50002],ph[50002],d[50002],i8,lh,nv,viz[50002],dv,nn,dn,aux;   
void pune();   
void hd(long int ic);   
void hu(long int ic);   
void sh(long int i1,long int i2);   
int main()   
{   
    FILE *f,*g;f=fopen("dijkstra.in","r");g=fopen("dijkstra.out","w");   
    fscanf(f,"%ld%ld",&n,&m);i8=1000000000;   
    for(i=1;i<=m;i++){fscanf(f,"%ld%ld%ld",&a,&b,&c);pune();}   
    for(i=1;i<=n;i++){h[i]=i;ph[i]=i;d[i]=i8;}d[1]=0;lh=n;   
    while(lh&&d[h[1]]<i8)   
    {  nv=h[1];viz[nv]=1;dv=d[nv];h[1]=h[lh];ph[h[1]]=1;lh--;hd(1);   
       pp=prim[nv];   
       while(pp)   
       { nn=pp->info;dn=pp->dist;   
         if(viz[nn])pp=pp->next;   
         else  
         { if(d[nn]>dv+dn)   
           { d[nn]=dv+dn;hu(ph[nn]);}   
           pp=pp->next;   
         }   
       }   
    }   
    for(i=2;i<=n;i++)   
    { if(d[i]==i8)d[i]=0;   
      fprintf(g,"%ld ",d[i]);   
    }   
    fprintf(g,"\n");fcloseall();return 0;   
}   
void pune()   
{   
    nod *paux;   
    paux=new nod;   
    paux->info=b;   
    paux->dist=c;   
    if(!prim[a]){paux->next=0;prim[a]=paux;return;}   
    paux->next=prim[a];prim[a]=paux;   
}   
void hd(long int ic)   
{   
    long int is,is1;   
    is=ic<<1;is1=is+1;
    if(is>lh)return;   
    if(is<lh)if(d[h[is1]]<d[h[is]])is=is1;   
    if(d[h[is]]<d[h[ic]]){sh(is,ic);hd(is);}   
}   
void hu(long int ic)   
{   
    long int is;   
    is=ic>>1;
    if(!is)return;   
    if(d[h[is]]>d[h[ic]]){sh(is,ic);hu(is);}   
}   
void sh(long int i1,long int i2)   
{   
    aux=h[i1];h[i1]=h[i2];h[i2]=aux;   
    ph[h[i1]]=i1;ph[h[i2]]=i2;   
}