#include<stdio.h>

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

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

typedef struct lista{
  long nod,cost;
  struct lista *next;
};

lista* p[50001];

long n, m, cont;
long heap[50001], nodul[50001], pozitie[50001], minim[50001], util[50001];

void readValues();

void solveFunction();

void printSolution();

void urcaHeap(long);

void coboaraHeap(long);

void schimba(long&, long&);

int main(){
  readValues();
  solveFunction();
  fclose(fin);
  fclose(fout);
  return 0;
}

void readValues()
{
  long val1, val2, val3;

  lista* adr;

  fscanf (fin, "%ld %ld", &n, &m);
  for(long i=1; i<=m; ++i)
  {
    fscanf (fin, "%ld %ld %ld", &val1, &val2, &val3);
    adr = new lista;
    adr -> nod = val2;
    adr -> cost = val3;
    adr -> next = p[ val1 ];
    p[ val1 ] = adr;
  }

}

void solveFunction()
{
  lista* adr;

  long curent;

  for(long i=1; i<=n; ++i)
  {
    heap[ i ] = INFI;
    nodul[ i ] = -1;
    pozitie[ i ] = -1;
    util[ i ] = 0;
  }
  adr = p[ 1 ];
  cont = 0;
  util[ 1 ] = 1;

  while( adr != NULL)
  {
    heap[ ++cont ] = adr -> cost;
    nodul[ cont ] = adr -> nod;
    pozitie[ adr -> nod ] = cont;
    util[ adr -> nod ] = 1;
    urcaHeap (cont);
    adr = adr -> next;
  }

  while( cont > 0 )
  {
    curent = nodul[ 1 ];
    minim[ curent ] = heap[ 1 ];
    pozitie[ curent ] = 0;
    nodul[ 1 ] = nodul[ cont ];
    heap[ 1 ] = heap[ cont ];
    pozitie[ nodul[ cont ] ] = 1;
    nodul[ cont ] = INFI;
    heap[ cont ] = INFI;
    --cont;
    
    coboaraHeap (1);

    adr = p[ curent ];
    
    while( adr != NULL)
    {

      if(util[ adr -> nod ])
      {
	if( minim[ curent ] + adr -> cost < heap[ pozitie[ adr -> nod] ])
	{
	  heap[ pozitie[ adr -> nod ] ] = minim[ curent ] + adr -> cost;
	  urcaHeap ( pozitie[ adr -> nod ] );
	}
      }

      else
      {
	  heap[ ++cont ] = adr -> cost + minim[ curent ];
          nodul[ cont ] = adr -> nod;
          pozitie[ adr -> nod ] = cont;
          util[ adr -> nod ] = 1;
          urcaHeap (cont);
      }

      adr = adr -> next;
    }
  }

  printSolution ();

}

void printSolution()
{

  for( long i=2; i <= n; ++i)
    fprintf(fout, "%ld ", minim[ i ]);

  fprintf(fout, "\n");

}

void urcaHeap(long poz)
{

  while( poz >= 1)
  {

    if(heap[ poz/2 ] > heap[ poz ])
    {
      schimba( heap[ poz/2 ], heap[ poz ]);
      schimba( nodul[ poz/2 ], nodul[ poz ]);
      schimba( pozitie[ nodul[ poz/2 ] ], pozitie[ nodul[ poz ] ]);
      poz /= 2;
    }
    else break;
  }

}

void coboaraHeap(long poz)
{
  long pozitia = 0;

  while( poz <= cont )
  {

    if( 2*poz <= cont)
    {
      pozitia = 2*poz;

      if( pozitia + 1 <= cont && heap[ pozitia + 1 ] < heap[ pozitia ])
	++pozitia;

    }
    else break;

    if( heap[ pozitia ] < heap[ poz ] )
    {
      schimba( heap[ pozitia ], heap[ poz ] );
      schimba( nodul[ pozitia ], nodul[ poz ] );
      schimba( pozitie[ nodul[ pozitia ] ], pozitie[ nodul[ poz ] ]);
      poz = pozitia;
    }
    else break;

  }

}

void schimba(long& val1, long& val2)
{

  val1 = val1 + val2;
  val2 = val1 - val2;
  val1 = val1 - val2;

}