#include<stdio.h>

#define max 50001
#define infinit 1<<30

struct nod{long int nd,inf; nod *urm;} *p[max];
long int n,s[max],d[max];

void dijkstra();

int main()
{
    FILE * f=fopen("dijkstra.in","r");
     long int x,y,z;
     long int m,i;
     nod *c;
     
     fscanf(f,"%ld %ld",&n,&m);
     
     for(i=1;i<=m;i++)
     {
        fscanf(f,"%ld %ld %ld",&x,&y,&z);
     
        c=new nod; 
        c->inf=z;
        c->nd=y;
        c->urm=p[x];
        p[x]=c;
     }
     
     fclose(f);
     
    dijkstra();
    
    f=fopen("dijkstra.out","w");
     for(i=2;i<=n;i++)
       fprintf(f,"%ld ",d[i]==infinit ? 0 : d[i]);
 
     fprintf(f,"\n");
     fclose(f);
    
    return 0;
}

void dijkstra()
{
     long int j,i,min,poz=0;
     nod *c;
     
     for(i=1;i<=n;i++)
       d[i]=infinit;
     for(c=p[1];c;c=c->urm)
        d[c->nd]=c->inf;
     
     for(i=2;i<=n;i++)
     {
          for(j=1,min=infinit;j<=n;j++)
            if(!s[j] && min>d[j] && d[j]!=infinit)
                  min=d[j],poz=j;
     
          if(min!=infinit)
          {
            s[poz]=1;
            for(c=p[poz];c;c=c->urm)
              if((d[poz]+c->inf<d[c->nd] || d[c->nd]==infinit) && d[c->nd]!=1)
                  d[c->nd]=d[poz]+c->inf;
          }
      }
}