#include<fstream.h>

#define xn 50001

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

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

int extrage_minimul();
void sus(int);
void jos(int);
void schimba(int,int);
void dijkstra(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 ? 0 : d[i])<<' ';
    fout<<'\n';
    
    fout.close();
    return 0;
}

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

int extrage_minimul()
{
    int pos=h[1];
    poz[h[1]]=0;
    poz[h[nr]]=1;
    h[1]=h[nr];
    h[nr]=0;
    nr--;
    jos(1);
    return pos;
}
    

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

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

void jos(int i)
{
     int min=0;
     if(h[2*i] && h[2*i+1])
        min=(d[h[2*i]]<d[h[2*i+1]] ? 2*i : 2*i+1);
     else
        if(h[2*i] && !h[2*i+1])
           min=2*i;
        else
           if(!h[2*i] && h[2*i+1])
              min=2*i+1;
     if(min==0) return;
     
     if(d[h[i]]>d[h[min]])
     {
       schimba(i,min);
       jos(min);
     }
}