#include <stdio.h>
long a[3][500001],st[50001],fin[50001],c[1000001],l,q,i,s,n,m,x,y,v[50001],z;
int main()
{freopen("dijkstra.in","r",stdin);freopen("dijkstra.out","w",stdout);
 fscanf(stdin,"%ld%ld",&n,&m);
 for(i=1;i<=m;i++)
  {fscanf(stdin,"%ld%ld%ld",&x,&y,&z);
   if(fin[x]==0){st[x]=fin[x]=l+1;l++;a[1][l]=y;a[0][l]=z;}
	  else{a[2][fin[x]]=l+1;fin[x]=l+1;l++;a[1][l]=y;a[0][l]=z;}
  }
 v[1]=0;c[1]=1;q=1;l=1;
 for(i=2;i<=n;i++)v[i]=2000000000;
 while(q<l&&c[q])
  {x=st[c[q]];
   while(x)
    {if(v[a[1][x]]>v[c[q]]+a[0][x]){l++;c[l]=a[1][x];v[a[1][x]]=v[c[q]]+a[0][x];}
     x=a[2][x];
    }
   q++;
  }
 for(i=2;i<=n;i++)if(v[i]==2000000000)fprintf(stdout,"0 ");else fprintf(stdout,"%ld ",v[i]);
 fclose(stdin);fclose(stdout);
 return 0;
}