#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 citire();
void dijkstra();
void afisare();

int main()
{
    citire();
    dijkstra();
    afisare();
    
    return 0;
}

void dijkstra()
{
     long int j,i,min,poz=0;
     nod *c;
     
     for(i=2;i<=n;i++)
       d[i]=infinit;
     
     for(i=1;i<=n;i++)
     {
          for(j=1,min=infinit;j<=n;j++)
            if(!s[j] && min>d[j])
                  min=d[j],poz=j;
     
          s[poz]=1;
          for(c=p[poz];c;c=c->urm)
              if(d[poz]+c->inf<d[c->nd])
                  d[c->nd]=d[poz]+c->inf;
      }
}    
       
void afisare()
{
     FILE *f=fopen("dijkstra.out","w");
     long int i;
 
     for(i=2;i<=n;i++)
       fprintf(f,"%ld ",d[i]==-1?0:d[i]);
 
     fprintf(f,"\n");
     fclose(f);
}

void citire()
{
     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);
}