#include<fstream.h>

#define xn 50001

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

struct lista { int nd,c; lista *urm; } *g[xn];
int n,m,t[xn],d[xn],h[xn],poz[xn],nr;

void hsus(int);
void hjos(int);
int hmin();
void dijkstra(int);
inline void schimba(int,int);

int main()
{
    int i,x;
    lista *p;
    
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
      p=new lista;
      fin>>x>>p->nd>>p->c;
      p->urm=g[x];
      g[x]=p;
    }
    
    dijkstra(1);
    
    for(i=2;i<=n;i++)
      fout<<(d[i]!=-1 ? d[i] : 0)<<' ';
    fout<<'\n';
    
    fout.close();
    return 0;
}

void dijkstra(int s)
{
     int pos;
     lista *p;
     
     memset(t,0,sizeof(t));
     memset(d,-1,sizeof(d));
     memset(poz,0,sizeof(poz));
     
     for(nr=0,p=g[s];p;p=p->urm)
     {
        d[p->nd]=p->c;
        t[p->nd]=s;
        h[++nr]=p->nd;
        poz[p->nd]=nr;
        hsus(nr);
     }
     
     while(nr)
     {
       pos=hmin();
       
       for(p=g[pos];p;p=p->urm)
          if(d[p->nd]==-1)
          {
            d[p->nd]=d[pos]+p->c;
            t[p->nd]=pos;              
            h[++nr]=p->nd;
            poz[p->nd]=nr;
            hsus(nr);
          }
          else
             if(d[p->nd]>d[pos]+p->c)
             {
               d[p->nd]=d[pos]+p->c;
               t[p->nd]=pos;
               if(poz[p->nd])
                 hsus(poz[p->nd]);
             }
     }
}

inline void schimba(int i,int j)
{
     int aux;
     aux=poz[i];
     poz[i]=poz[j];
     poz[j]=aux;
     
     aux=h[i];
     h[i]=h[j];
     h[j]=aux;
}

void hsus(int i)
{
     int k=i/2;
     
     if(k && d[h[k]]>d[h[i]])
        schimba(k,i);
}

void hjos(int i)
{
     if((d[h[2*i]]<=d[h[2*i+1]] && h[2*i] && h[2*i+1]) || (!h[2*i+1] && h[2*i]))
     {
        schimba(i,2*i);
        hjos(2*i);
     }
     else
        if(h[2*i+1])
        {
           schimba(i,2*i+1);
           hjos(2*i+1);
        }
}
          
int hmin()
{
    nr--;
    int pos=h[1];
    h[1]=0;
    poz[pos]=0;
    hjos(1);
    return pos;
}