#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;
    ifstream fin(in);
    ofstream fout(out);
    
    fin >> N >> M;
    for ( int i = 1; i <= M; i++ )
    {
        fin >> 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;
                       last++, Q2[last] = q->vf;
                  }
              }
          }
          
          act = last, last = 0;
          memcpy( Q1, Q2, sizeof(Q1[0])*(act+1) );
    }
    
    for ( int i = 2; i <= N; i++ )
    {
        if ( D[i] == infinit ) fout << "0 ";
        else fout << 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;
}