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

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

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

PNOD L[dim];
int N, M;
int D[dim], Q1[dim], Q2[dim], Sel[dim];

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 ( int i = 1; i <= M; i++ )
    {
        scanf("%d%d%d", &X, &Y, &C);
        Add(X,Y,C);
    }
    
    int act, last, nod;
    
    for ( int i = 1; i <= N; i++ ) D[i] = infinit, Sel[i] = 0;
    
    D[1] = last = 0;
    Q1[act=1] = 1;
    
    while ( act )
    {
          for ( int s = 1; s <= act; s++ )
          {
              nod = Q1[s];
              for ( PNOD q = L[nod]; q; q=q->next )
              {
                  if ( D[q->vf] > D[nod] + q->cost )
                  {
                       D[q->vf] = D[nod] + q->cost;
                       if ( !Sel[q->vf] ) last++, Q2[last] = q->vf, Sel[q->vf] = 1;
                  }
              }
          }
          
          act = last, last = 0;
          for ( int s = 1; s <= act; s++ )
              Q1[s] = Q2[s], Sel[Q1[s]] = 0, Q2[s] = 0;
    }
    
    for ( int i = 2; i <= N; i++ )
    {
        if ( D[i] == infinit ) printf("0 ");
        else printf("%d ", 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;
}