#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define INPUT "dijkstra.in"
#define OUTPUT "dijkstra.out"
#define NMAX 50001
#define INFI 2000000000
#define lp vector< 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)
{
  long p = _X;

  while( p >= 1)
  {
    if(Final[ Heap[ p / 2 ] ] > Final[ Heap[ p ] ])
    {
      swap( Heap[ p / 2 ], Heap[ p ] );
      PHeap[ Heap[ p/2] ] = p/2;
      PHeap[ Heap[ p ] ] = p;

      p /=2;
    }
    else return;
  }
}

void ExtractHeap(long _X)
{
  long P;
  long p = _X;

  while(p <= Poz)
  {
    if(2 * p <= Poz)
    {
      P = 2 * p;
      
      if(P + 1 <= Poz && Final[ Heap[ P + 1 ] ] < Final[ Heap[ P ]])
        ++P;

      if(Final[Heap[ P ]] < Final[Heap[ p ]])
      {
        swap( Heap[ P ], Heap[ p ] );
        PHeap[ Heap[ P ] ] = P;
        PHeap[ Heap[ p ] ] = p;

	p = P;
      }
      else return;
    }
    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 = 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;
}