#include<fstream.h>

#define max_n 50001
#define infinit 1<<30

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

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

void citire()
{
     nod *c;
     fin>>n>>m;
     int x,y,z;
     while(fin>>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++)
     fout<<d[i]<<' ';
    fout<<'\n';
    fout.close();
    return 0;
}