#include<stdio.h>

#define max_n 50001
#define infinit 1<<30

FILE *in=fopen("dijkstra.in","r");
FILE *out=fopen("dijkstra.out","w");

struct nod{int nd,inf; nod *urm;} *l[max_n];
int d[max_n],v[max_n],n,m;

void citire()
{
     nod *c;
     fscanf(in,"%d %d",&n,&m);

     int x,y,z;
     for(int i=1;i<=m;i++)
     {
        fscanf(in,"%d %d %d",&x,&y,&z);     
        c=new nod;
        c->nd=y;
        c->inf=z;
        c->urm=l[x];
        l[x]=c;
     }
}

int main()
{
    citire();
    int i,min,poz;
    nod *c;
    
    for(i=1;i<=n;i++)
       d[i]=infinit;
    for(c=l[1];c;c=c->urm)
       d[c->nd]=c->inf;
    v[1]=1;
    for(i=1;i<n;i++)
    {
       min=infinit;
       for(int j=1;j<=n;j++)
          if(!v[j] && min>d[j])
              min=d[j],poz=j;
       if(min!=infinit)
       {
          v[poz]=1;
          for(c=l[poz];c;c=c->urm)
             if(d[poz]+c->inf<d[c->nd])
                d[c->nd]=d[poz]+c->inf;
       }
    }
    
    for(i=2;i<=n;i++)
     fprintf(out,"%d ",d[i]);
    fprintf(out,"\n");
    
    fclose(out);
    return 0;
}