#include <stdio.h>
#include <fstream>
using namespace std;

#define in "dijkstra.in"
#define out "dijkstra.out"
#define dim 50001
#define infinit (1<<30)
#define SET(A,c) for( int i = 1; i <= N; i++ ) A[i] = c;

int N, M;
int D[dim];

typedef struct NOD {
     int vf, cost;
     NOD* next;
} *PNOD;

PNOD L[dim];

int aux, size, act, last;
int H[dim], Pos[dim], Sel[dim];

void MoveUp(int);
void MoveDown(int);
void Swap(int,int);
void Add(int,int,int);

int main()
{
    int x, y, c;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &N, &M);
    for ( ; M; M-- )
        scanf("%d%d%d", &x, &y, &c), Add(x,y,c);
    
    SET(Sel,0); 
    SET(D,(1<<20));
    
    for ( int i = 1; i <= N; i++ )
        H[i] = Pos[i] = i;
    
    size = N;
    D[1] = 0;
    
    while ( size )
    {
          int nod = H[1];
          Sel[nod] = 0, H[1] = H[size], Pos[H[1]] = 1, size--;
          
          MoveDown(H[1]);
          for ( PNOD q = L[nod]; q; q=q->next )
              if ( D[q->vf] > D[nod] + q->cost )
              {
                   D[q->vf] = D[nod] + q->cost;
                   MoveUp(q->vf);
              }
    }
    
    for ( int i = 2; i <= N; i++ )     
        printf("%d ", D[i]==(1<<30) ? 0 : D[i] );
}

void Add(int i, int j, int c)
{
     PNOD q = new NOD;
     q->vf = j, q->cost = c;
     q->next = L[i], L[i] = q;
}

void Swap(int nod1, int nod2)
{
     aux = H[nod1], H[nod1] = H[nod2], H[nod2] = aux;
}

void MoveDown(int nod)
{
     act = Pos[nod], last = (act<<1);
     
     while ( act <= size )
     {
           if ( last < size )
              if ( D[H[last]] > D[H[last+1]] ) last++;
           
           if ( D[H[act]] > D[H[last]] )
           {
                Pos[H[act]] = last, Pos[H[last]] = act;
                Swap(act,last);
                act = last, last <<= 1;
           }
           else break;
     }
}

void MoveUp(int nod)
{
     act = Pos[nod], last = act/2;
     
     while ( 1 )
     {
           if ( D[H[act]] < D[H[last]] )
           {
                Pos[H[act]] = last, Pos[H[last]] = act;
                Swap(act,last);
                act = last, last /= 2;
           }
           else break;
           
           if ( act == 1 ) break;
     }
}