#include<cstdio>
#include<algorithm>

using namespace std;

#define INPUT "dijkstra.in"
#define OUTPUT "dijkstra.out"
#define INFI 2000000000
#define NMAX 50002

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

typedef struct Graph
{
  long node, cost;
  Graph *next;
};

Graph *List[ NMAX ];
long N, M, Nmax;
long Heap[ NMAX ], Poz[ NMAX ], NodHeap[ NMAX ], Minim[ NMAX ];

void readValues()
{
  Graph *adr;
  long a, b, c;

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

  for(long i = 1; i <= M; ++i)
  {
    fscanf(fin, "%ld %ld %ld", &a, &b, &c);

    adr = new Graph;
    adr -> node = b;
    adr -> cost = c;
    adr -> next = List[ a ];
    List[ a ] = adr;
  }
}

void UpHeap(long p)
{
  while( p > 1)
  {
    if(Heap[ p / 2 ] > Heap[ p ])
    {
      swap( Heap[ p / 2 ], Heap[ p ] );
      swap( NodHeap[ p / 2 ], NodHeap[ p ]);
      swap( Poz[ NodHeap[ p / 2 ] ], Poz[ NodHeap[ p ] ]);

      p /=2;
    }
    else return;
  }
}

void DownHeap(long p)
{
  long P;

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

      if(Heap[ P ] < Heap[ p ])
      {
        swap( Heap[ P ], Heap[ p ] );
        swap( NodHeap[ P ], NodHeap[ p ]);
        swap( Poz[ NodHeap[ P ] ], Poz[ NodHeap[ p ] ]);

	p = P;
      }
      else return;
    }
    else return;
  }
}

void InitMin()
{
  for(long i = 1; i <= N; ++i)
  {
    Minim[ i ] = INFI;
    Poz[ i ] = -1;
  }
}

void solveFunction()
{
  Graph *adr;
  long Actual, T;

  InitMin();

  Heap[ 1 ] = 0, NodHeap[ 1 ] = 1, Poz[ 1 ] = 1;
  Nmax = 1;
  
  while( Nmax > 0 )
  {
    Actual = NodHeap[ 1 ], Minim[ Actual ] = Heap[ 1 ];
    Heap[ 1 ] = Heap[ Nmax ], NodHeap[ 1 ] = NodHeap[ Nmax ], Poz[ NodHeap[ 1 ] ] = 1;

    --Nmax;

    DownHeap(1);

    adr = List[ Actual ];

    while( adr != NULL)
    {
      if( Minim[ adr -> node ] == INFI)
      {
	if( Poz[ adr -> node ] == -1 )
	{
	  Heap[ ++Nmax ] = Minim[ Actual ] + adr -> cost;
	  NodHeap[ Nmax ] = adr -> node, Poz[ NodHeap[ Nmax ] ] = Nmax;

	  UpHeap( Nmax );
	}
	else
        if( Heap[ Poz[ adr -> node ] ] > (T = Minim[ Actual ] + adr -> cost))
	{
          Heap[ Poz[ adr -> node ] ] = T;
	  
	  UpHeap( Poz[ adr -> node ] );
	}
      }

      adr = adr -> next;
    }
  }

  for(long i = 2; i <= N; ++i)
    if(Minim[ i ] == INFI)
      fprintf(fout, "0 ");
    else
      fprintf(fout, "%ld ", Minim[ i ]);

  fprintf(fout, "\n");
}

int main()
{
  readValues();

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}