#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)
       {
	 if(viz[pp->info])pp=pp->next;
	 else
	 { if(d[pp->info]>dv+pp->dist)
	   { d[pp->info]=dv+pp->dist;hu(ph[pp->info]);}
	   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;
}