#include <stdio.h>

const int nmax = 50001;
const int INF = 1 << 30;
int N,M,k,d[nmax],h[nmax],poz[nmax];
struct graf  {int nod,cost;
              graf *urm;} *G[nmax];


void add(int where,int what,int cost)
     {graf *q=new graf;
      q->nod=what;
      q->cost=cost;
      q->urm=G[where];
      G[where]=q;
     }
void read()       
     {freopen("dijkstra.in","r",stdin);
      int i,x,y,c;
      scanf("%d %d",&N,&M);
      for(i=1;i<=M;i++)
           {scanf("%d %d %d",&x,&y,&c);
            add(x,y,c);
           }
      fclose(stdin);
      }
void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void push(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( d[ h[tata] ] > d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;

            swap(tata, what);

            what = tata;
        }
        else
            what = 1;
    }
}

void pop(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else     break;

        if ( d[ h[what] ] > d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;

            swap(what, f);

            what = f;
        }
        else      break;
    }
}
void dijkstra()
     {int i,indmin;
     
      for(i=2;i<=N;i++)    {d[i]=INF;poz[i]=-1;}
      
      h[++k]=k;poz[k]=k;    //initializare heap
     
      while(k)
          {indmin=h[1];     //scoatere radacina
           swap(1,k);
           poz[h[1]]=1;
           k--;
           pop(1);
           
           graf *p=G[indmin];
           
           while(p)
                {if(d[p->nod]>d[indmin]+p->cost)
                                {d[p->nod]=d[indmin]+p->cost;
                                
                                 if(poz[p->nod]!=-1)    push(poz[p->nod]);   
                                 
                                 else                  {h[++k]=p->nod;
                                                        poz[h[k]]=k;
                                                        push(k);
                                                       }
                                }
                p=p->urm;
                } 
           } 
      }
void write()
     {freopen("dijkstra.out","w",stdout);
      int i;
      for(i=2;i<=N;i++)   printf("%d ",d[i] == INF ? 0 : d[i]);
      printf("\n");
      fclose(stdout);
      }
int main()
    {read();
     dijkstra();
     write();
     return 0;
     }