#include<stdio.h>
long int n,m,i,a,b,c,h[50002],ph[50002],d[50002],i8,
*vec[50002],*cost[50002],lh,nv,viz[50002],dv,nn,dn,aux,gr[50002];
void citire();
void pune();
void hd(long int ic);
void hu(long int ic);
void sh(long int i1,long int i2);
int main()
{
    FILE *g=fopen("dijkstra.out","w");
    citire();
    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);
       for(i=gr[nv];i>=1;i--)
       { nn=vec[nv][i];
	 if(viz[nn])continue;
	 if(d[nn]>dv+cost[nv][i])
	   { d[nn]=dv+cost[nv][i];hu(nn);}
       }
    }
    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 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;
}
void citire()
{
	FILE *f=fopen("dijkstra.in","r");
	fscanf(f,"%ld%ld",&n,&m);i8=1000000000;
	for(i=1;i<=m;i++){fscanf(f,"%ld%ld%ld",&a,&b,&c);gr[a]++;}
	fclose(f);
	for(i=1;i<=n;i++)
	{ vec[i]= new long [gr[i]+2];
	  cost[i]= new long [gr[i]+2];
	  gr[i]=0;
	}
	f=fopen("dijkstra.in","r");
	for(i=1;i<=m;i++)
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=m;i++)
	 { fscanf(f,"%ld%ld%ld",&a,&b,&c);
	   vec[a][++gr[a]]=b;
	   cost[a][gr[a]]=c;
	 }
	fclose(f);
}