#include <fstream>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

#define MAX_N 50002
#define MAX_M 250002
#define INF 250000000


struct muchie
{
  int cost;
  int nod;
  muchie(int n,int c):cost(c),nod(n){} 
};

map<int, vector<muchie> > muchii;

int heap[MAX_N];
int poz_h[MAX_N]; //poz_h[k] spune pozitia elementului k in heap (pentru o gasire mai usoara)
int heaps;        //heap size. Primul element din heap este pe pozitia 1
int d[MAX_N]; /** distanta minima */


/*
face swap la 2 noduri in heap cu actualizare
*/
void swap_heap(int nod1,int nod2)
{ 

  swap(heap[poz_h[nod1]],heap[poz_h[nod2]]);
  swap(poz_h[nod1],poz_h[nod2]);
}

/**
  impinge in heap si pastreaza proprietatea de heap
*/
void push_heap(int node)
{
  heaps ++;
  heap[heaps] = node;
  poz_h[node] = heaps;

  /** pozitia elementului in heap */
  int elem = heaps;
  /* restauram proprietatea de heap  */
  while(1)
  {
     if(elem == 1)
       break;

     int tatal = elem/2;
     if(d[heap[tatal]] > d[heap[elem]])
       swap_heap(node,heap[tatal]);
     else
       break;

     elem = tatal;
  }
}

/**
  pop de pe heap si restaureaza proprietatea de heap
*/
void pop_heap()
{
  if(heaps == 0)
    return ;
  poz_h[heap[heaps]] = 1;
  heap[1] = heap[heaps];
  heaps--;

  int elem = 1;
  while(1)
  {
    int elem1 = elem*2;
    int elem2 = elem*2+1;
    
    if(elem1 <=heaps)
    if(d[heap[elem]] > d[heap[elem1]])
    {
      swap_heap(heap[elem],heap[elem1]);
      elem = elem1;
      continue;
    }

    if(elem2 <= heaps)
    if(d[heap[elem]] > d[heap[elem2]])
    {
      swap_heap(heap[elem],heap[elem2]);
      elem = elem2;
      continue;
    }

    if(elem1>heaps || elem2>heaps)
      break;

    if(d[heap[elem]] <= d[heap[elem1]] && d[heap[elem]] <= d[heap[elem2]])
      break;
  }
}


void promote_heap(int node)
{
  int pos_elem = poz_h[node];

  while(1)
  {
    if(pos_elem == 1)
      break;
    int tatal = pos_elem/2;

    if(d[heap[tatal]] < d[heap[pos_elem]])
      swap_heap(node,heap[tatal]);
    else
      break;
  }
}

void show_heap()
{
  for(int i = 1;i<=heaps; i++)
    cout<<heap[i]<<" ";
}

int main()
{
  int noduri,much;
  ifstream fin("dijkstra.in");
  ofstream fout("dijkstra.out");

  fin>>noduri>>much;
  for(int i=1; i<=much; i++)
  {
    int n1,n2,c;
    fin>>n1>>n2>>c;
    ::muchii[n1].push_back(muchie(n2,c));
  }
  
  /*heap[1] = muchii[1][0].nod;
  poz_h[muchii[1][0].nod] = 1;
  heaps = 1;*/


  for(unsigned int i = 0; i<muchii[1].size(); i++)
  {
    d[muchii[1][i].nod] = muchii[1][i].cost;
    push_heap(muchii[1][i].nod);
  }


  /**
    punem in heap nodurile care nu au legatura directa catre element
  */
  for(int i = 2; i<=noduri; i++)
    if(poz_h[i] == 0)
    {
      d[i] = INF;
      push_heap(i);
    }


  for(int i = 2; i<=noduri; i++)
  {
    int k = heap[1];
    pop_heap();

    for(unsigned int i = 0; i<muchii[k].size(); i++)
      if(d[muchii[k][i].nod] > d[k] + muchii[k][i].cost)
      {
        d[muchii[k][i].nod] = d[k]+muchii[k][i].cost;
        promote_heap(muchii[k][i].nod);
      }
  }

  for(int i = 2; i<=noduri;i++)
    if(d[i] == INF)
      fout<<0<<" ";
    else
      fout<<d[i]<<" ";


  return 0;
}