#include<stdio.h>
int n,m,i,a[25005],b[25005],v[25005],d[25005],ve;
int main()
{
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 scanf("%d%d",&n,&m);
 for(i=1;i<=m;++i)
    {scanf("%d%d%d",&a[i],&b[i],&v[i]);
     if(a[i]==1)d[b[i]]=v[i];}
 for(i=2;i<=n;++i)if(!d[i])d[i]=25000;
 d[1]=0;
 ve=1;
 while(ve)
  {ve=0;
   for(i=1;i<=m;++i)
      if(d[b[i]]>d[a[i]]+v[i])d[b[i]]=d[a[i]]+v[i],ve=1;/*
  min=2147100000;
   nod=0;
   for(i=1;i<=n;++i)if(d[i]<min&&!viz[i])min=d[i],nod=i;
   viz[nod]=1;
   ++ve;
   for(i=1;i<=m;++i)
      if(a[i]==nod)
        if(!viz[b[i]])
          if(v[i]+d[nod]<d[b[i]])d[b[i]]=v[i]+d[nod];     */
  }
 for(i=2;i<=n;++i)
    if(d[i]==25000)printf("0 ");
                   else printf("%d ",d[i]);
 printf("\n");
 return 0;
}