#include<fstream>
using namespace std;

const int inf = 1<<30;
#define MAX 50000

typedef struct graf
{
   int nod,et;
   graf* next;
}graf;

int N,M,d[MAX];
int nr;
graf* a[MAX];
int minHeap[MAX];
int heapSize;
int poz[MAX];
bool T[MAX];

void adaug(int x,int y,int et)
{
   graf* aux = new graf();
   aux->et=et;
   aux->nod = y;
   aux->next = a[x];
   a[x] = aux;
}

void shiftUp(int i)
{
   int parent,aux;
   if(i!=0)
   {
      parent = (i-1)/2;
      if(d[minHeap[parent]] > d[minHeap[i]])
      {
         aux = minHeap[i];
         minHeap[i] = minHeap[parent];
         minHeap[parent] = aux;
         poz[minHeap[i]] = parent;
         poz[minHeap[parent]] = i;
         shiftUp(parent);
      }
   }
}

void insertHeap(int i)
{
   minHeap[heapSize] = i;
   poz[i] = heapSize;
   shiftUp(heapSize++);
}

void shiftDown(int i)
{
   int aux;
   int child = i*2+1;
   if(child<heapSize)
   {
      if(d[minHeap[i]] > d[minHeap[child]])
      {
         aux = minHeap[i];
         minHeap[i] = minHeap[child];
         minHeap[child] = aux;
         poz[minHeap[i]] = child;
         poz[minHeap[child]] = i;
         shiftDown(child);
      }
      else
      {
         child++;
         if(child<heapSize && d[minHeap[i]] > d[minHeap[child]])
         {
            aux = minHeap[i];
            minHeap[i] = minHeap[child];
            minHeap[child] = aux;
            poz[minHeap[i]] = child;
            poz[minHeap[child]] = i;
            shiftDown(child);
         }
      }
   }
}

void removeHeap()
{
   minHeap[0] = minHeap[--heapSize];
   shiftDown(0);
}

void citire()
{
   ifstream f("dijkstra.in");
   f>>N>>M;
   int x,y,z;

   for(int i=0;i<M;i++)
   {
      f>>x>>y>>z; 
      adaug(x-1,y-1,z);
   }
   f.close();

  for(int i=1;i<N;i++)
   {
      T[i] = false;
      d[i] = inf; 
   }

   graf* aux = new graf();
   aux = a[0];
   while(aux)
   {
      d[aux->nod] = aux->et;
      aux = aux->next;
   }
   
   for(int i=1;i<N;i++)
      insertHeap(i);

   T[0] = true;
   nr = 1;
};

void solve()
{
   int xp;
   while(nr<N)
   {
      xp = minHeap[0];
      T[xp] = true;
      removeHeap();
      nr++;
      graf* aux = new graf();
      aux = a[xp];
      while(aux)
      {
         if(!T[aux->nod] && d[aux->nod]>d[xp]+aux->et)
         {
            d[aux->nod] = d[xp]+aux->et;
            shiftUp(poz[aux->nod]);
         }
         aux= aux->next;
         
      }
   }
   
   ofstream g("dijkstra.out");
   for(int i=1;i<N;i++)
      if(d[i]!=inf)
         g<<d[i]<<" ";
      else 
         g<<"0 ";
   g.close();
}

int main()
{
   citire();
   solve();
   return 0;
}