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

#define in "dijkstra.in"
#define out "dijkstra.out"
#define dim 50001
#define infinit (1<<30)

int N, M, aux;
int D[dim];

int hsize=0, act, last;
int H[dim], Poz[dim], Sel[dim];

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

PNOD L[dim];

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

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 = 0; i <= N; D[++i] = infinit, Sel[i] = 0 ) ; 
    
    int minim, nod;
    
    D[1] = 0;
    H[++hsize] = 1, Poz[1] = 1, Sel[1] = 1;
    
    while ( hsize )
    {
          nod = H[1], minim = D[nod];
          GetMin();
          if ( hsize > 0 ) MoveDown();
          
          for ( PNOD q = L[nod]; q; q=q->next )
          {
              if ( D[q->vf] > minim + q->cost )
              {
                   D[q->vf] = minim + q->cost;
                   if ( Sel[q->vf] ) MoveUp(q->vf);
                   else
                   {
                       ++hsize, Sel[q->vf] = 1, H[hsize] = q->vf, Poz[q->vf] = hsize;
                       MoveUp(q->vf);
                   }
              }
          }
    }
    
    for ( int i = 2; i <= N; i++ )
        printf("%d ", D[i] == infinit ? 0 : D[i]);
}

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

void Swap(int i, int j)
{
     aux = H[i], H[i] = H[j], H[j] = aux;
}

void MoveDown()
{
     act = 1, last = act*2;
     
     while ( act <= hsize )
     {
           if ( last < hsize )
              if ( D[H[last]] > D[H[last+1]] ) last++;
           
           if ( D[H[act]] > D[H[last]] )
           {
                Poz[H[act]] = last, Poz[H[last]] = act;
                Swap(act,last);
                act = last, last *= 2;
           }
           else break;
     }
}

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

void GetMin()
{
     H[1] = H[hsize];
     Poz[H[1]] = 1;
     hsize--;
}