#include<stdio.h>

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

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

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

Graph *List[ NMAX ];
long N, M, Nmax;
long heap[ NMAX ], nodHeap[ NMAX ], poz[ NMAX ], Minim[ NMAX ], util[ NMAX ];

void readValues()
{
  long X, Y, Z;
  Graph *adr;

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

  for(long i = 0; i < M; ++i)
  {
    fscanf(fin, "%ld %ld %ld", &X, &Y, &Z);

    adr = new Graph;
    adr -> node = Y;
    adr -> cost = Z;
    adr -> next = List[ X ];
    List[ X ] = adr;
  }
}

void swap(long &V1, long &V2)
{
  V1 = V1 + V2;
  V2 = V1 - V2;
  V1 = V1 - V2;
}

void upHeap(long p)
{
  while( p > 0 )
  {
    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( 2 * p + 1 <= Nmax)
        if(heap[ 2 * p ] > heap[ 2 * p + 1 ])
          P = 2 * p + 1;

      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;
  }
}

void solveFunction()
{
  Graph *adr;
  long cur;

  for(long i = 0; i <= N; ++i)
  {
    heap[ i ] = -1;
    poz[ i ] = -1;
    nodHeap[ i ] = -1;
  }

  adr = List[ 1 ];

  Nmax = 0;

  while(adr != NULL)
  {
    ++Nmax;
    heap[ Nmax ] = adr -> cost;
    nodHeap[ Nmax ] = adr -> node;
    poz[ adr -> node ] = Nmax;

    upHeap( Nmax);

    adr = adr -> next;
  }

  Minim[ 1 ] = 0;

  while(Nmax > 0)
  {
    cur = nodHeap[ 1 ];
    adr = List[ cur ];
    util[ cur ] = 1;
    Minim[ cur ] = heap[ 1 ];
    heap[ 1 ] = heap[ Nmax ];
    nodHeap[ 1 ] = nodHeap[ Nmax ];
    poz[ nodHeap[ 1 ] ] = 1;
    --Nmax;

    downHeap(1);

    while(adr != NULL)
    {
	if(poz[ adr -> node ] == -1)
	{
	  ++Nmax;
	  heap[ Nmax ] = Minim[ cur ] + adr -> cost;
	  nodHeap[ Nmax ] = adr -> node;
	  poz[ adr -> node ] = Nmax;

	  upHeap(Nmax);
	}
	else
	if(Minim[ cur ] + adr -> cost < heap[ poz[ adr -> node ]])
	{
	  heap[ poz[ adr -> node ] ] = Minim[ cur ] + adr -> cost;

	  upHeap( poz[ adr -> node ] );
	}

      adr = adr -> next;
    }
  }

  for(long i = 1; i < N; ++i)
    fprintf(fout, "%ld ", Minim[ i + 1 ]);

  fprintf(fout, "\n");
}

int main()
{
  readValues();

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}