#include<stdio.h>
#include<string.h>
int n,m,i,a[250005],b[250005],v[250005],d[50005],ve,j,l;
char sir[100];
int main()
{
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 scanf("%d%d\n",&n,&m);
 for(i=1;i<=m;++i)
    {gets(sir);
     scanf("\n");
     j=0;
     while(sir[j]!=' '){a[i]=a[i]*10+(long)(sir[j]-'0');++j;}
     ++j;
     while(sir[j]!=' '){b[i]=b[i]*10+(long)(sir[j]-'0');++j;}
     ++j;l=strlen(sir);
     while(j<l){v[i]=v[i]*10+(long)(sir[j]-'0');++j;}
     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;
}