#include<cstdio>
#include<list>
#include<algorithm>

using namespace std;

#define INPUT "dijkstra.in"
#define OUTPUT "dijkstra.out"
#define NMAX 50001
#define INFI 2000000000
#define lp list< pair< long, long > >
#define mp make_pair
#define pb push_back

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long N, M, Poz, Cont;
lp List[ NMAX ];
long Heap[ NMAX ], PHeap[ NMAX ], Final[ NMAX ];
int vis[ NMAX ];

void readData()
{
  long Node1, Node2, Cost;

  fscanf(fin, "%ld %ld", &N, &M);

  for(;M--;)
  {
    fscanf(fin, "%ld %ld %ld", &Node1, &Node2, &Cost);

    List[ Node1 ].pb(mp(Node2, Cost));
  }
}

void AddHeap(long _X)
{
  if(_X/2 < 1 || Final[ Heap[ _X/2 ] ] < Final[ Heap[ _X ] ])
    return;

  swap(Heap[ _X/2 ], Heap[ _X ]);
  PHeap[ Heap[ _X/2 ] ] = _X/2;
  PHeap[ Heap[ _X ] ] = _X;

  AddHeap(_X/2);
}

void ExtractHeap(long _X)
{
  if( 2 * _X > Poz) return;
  if( 2 * _X + 1 > Poz && Final[ Heap[ 2 * _X ] ] > Final[ Heap[ _X ] ]) return;
  if( 2 * _X + 1 <= Poz && Final[ Heap[ 2 * _X ] ] > Final[ Heap[ _X ] ] && Final[ Heap[ 2 * _X + 1 ] ] > Final[ Heap[ _X ] ]) return;

  if( 2 * _X + 1 > Poz)
  {
    if(Final[ Heap[ 2 * _X ] ] < Final[ Heap[ _X ] ])
    {
      swap(Heap[ 2 * _X ], Heap[ _X ]);
      PHeap[ Heap[ 2 * _X ] ] = 2 * _X;
      PHeap[ Heap[ _X ] ] = _X;

      ExtractHeap(2 * _X);
    }
  }
  else
  {
    if(Final[ Heap[ 2 * _X] ] < Final[ Heap[ 2 * _X + 1 ] ] && Final[ Heap[ 2 * _X ] ] < Final[ Heap[ _X ] ])
    {
      swap(Heap[ 2 * _X ], Heap[ _X ]);
      PHeap[ Heap[ 2 * _X ] ] = 2 * _X;
      PHeap[ Heap[ _X ] ] = _X;
      ExtractHeap( 2 * _X );
    }
    else
    if(Final[ Heap[ 2 * _X] ] > Final[ Heap[ 2 * _X + 1 ] ] && Final[ Heap[ 2 * _X + 1] ] < Final[ Heap[ _X ] ])
    {
      swap(Heap[ 2 * _X + 1], Heap[ _X ]);
      PHeap[ Heap[ 2 * _X + 1] ] = 2 * _X + 1;
      PHeap[ Heap[ _X ] ] = _X;
      ExtractHeap( 2 * _X + 1);
    }
    else return;
  }
}

void solve()
{
  for(long i = 1; i <= N; ++i)
    Final[ i ] = INFI, vis[ i ] = 0;

  Poz = 0;
  Cont = 0;
  long Node;

  Final[ 1 ] = 0;
  Heap[ ++Poz ] = 1;
  PHeap[ 1 ] = Poz;

  lp::iterator it;

  vis[ 1 ] = 1;

  while(Poz)
  {
    Node = Heap[ 1 ];
    Heap[ 1 ] = Heap[ Poz-- ];

    ExtractHeap(1);

    for(it = List[ Node ].begin(); it != List[ Node ].end(); ++it)
      if(!vis[ (*it).first ])
      {
        Heap[ ++Poz ] = (*it).first;
        vis[ (*it).first ] = 1;
        PHeap[ (*it).first ] = Poz;
        Final[ (*it).first ] = Final[ Node ] + (*it).second;
        AddHeap( Poz );
      }
      else
      if(Final[ (*it).first ] > Final[ Node ] + (*it).second)
      {
        Final[ (*it).first ] = Final[ Node ] + (*it).second;
        AddHeap( PHeap[ (*it).first ]);
      }
    for(long i = 1; i <= Poz; ++i)
      fprintf(stderr, "%ld ", Heap[ i ]);
    fprintf(stderr, "\n");
    for(long i = 1; i <= N; ++i)
      fprintf(stderr, "%ld ", Final[ i ]);
    fprintf(stderr, "\n");
  }

  for(long i = 2; i <= N; ++i)
    if(Final[ i ] != INFI) fprintf(fout, "%ld ", Final[ i ]);
    else fprintf(fout, "0 ");
  fprintf(fout, "\n");
}

int main()
{
  readData();

  solve();

  fclose(fin);
  fclose(fout);

  return 0;
}