#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);
    
    for ( int i = 1; i <= N; i++ )
        D[i] = infinit, 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(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(Pos[q->vf]);
              }
    }
    
    for ( int i = 2; i <= N; i++ )     
        printf("%d ", D[i] == infinit ? 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)
{
     Pos[H[nod1]] = nod2, Pos[H[nod2]] = nod1;
     aux = H[nod1], H[nod1] = H[nod2], H[nod2] = aux;
}

void MoveDown(int act)
{
     last = act<<1;
     if ( last > size || act > size ) return;
     if ( last < size && D[H[last]] > D[H[last+1]] ) last++;
     if ( D[H[act]] <= D[H[last]] ) return;
     
     Swap(act,last); 
     MoveDown(last);
}

void MoveUp(int act)
{
     last = act>>1;
     if ( act == 1 || last < 1 ) return;
     if ( D[H[act]] >= D[H[last]] ) return;
     
     Swap(act,last);
     MoveUp(last);
}