#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];
graf* a[MAX];


typedef struct FibHeap
{
   int index;
   bool mark;
   FibHeap* child,*father,*left,*right;
   int degree;
}FibHeap;

//int minHeap[MAX],heapSize,poz[MAX];
FibHeap* Min;
FibHeap* ARB[MAX];
int FibSize;
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 createFibHeap()
{
   Min = NULL;
   FibSize = 0;
}

void concatenate(FibHeap* x)
{
   if(!Min)
   {
      Min = x;
      x->left = Min;
      x->right = Min;
   }
   else
   {
      if(Min->left)
      {
         Min->left->right = x;
         x->left = Min->left;
         Min->left = x;
         x->right = Min;
      }
      else
      {
         Min->left = x;
         Min->right = x;
         x->left = Min;
         x->right = Min;
      }
      if(d[Min->index] > d[x->index])
         Min = x;
   }
}

void insertFibHeap(int index)
{
   FibHeap* x = new FibHeap();
   x->mark = false;
   x->child = NULL;
   x->father = NULL;
   x->left = NULL;
   x->right = NULL;
   x->degree = 0;
   x->index = index;
   
   concatenate(x);
   ARB[FibSize] = x;
   FibSize++;
}

void switchFibHeap(FibHeap* x, FibHeap* y)
{
   FibHeap * aux = x->right;
   x->right = y->right;
   x->right->left = x;
   y->right = aux;
   y->right->left = y;

   aux = x->left;
   x->left = y->left;
   x->left->right = x;
   y->left = aux;
   y->left->right = y;

}

void removeFromRootFibHeap(FibHeap* x)  //presupun ca mai exista cel putin un alt nod in root
{
   x->left->right = x->right;
   x->right->left = x->left;
   x->left = NULL;
   x->right = NULL;
}

void addChild(FibHeap* f, FibHeap* c)  //presupun ca c nu are left si right
{
   if(f->child)
   {
      f->child->left->right = c;
      c->left = f->child->left;
      c->right = f->child;
      f->child->left = c;
   }
   else
   {
      f->child = c;
      c->left = c;
      c->right = c;
   }
   c->father = f;
   f->degree++;
}

void FibHeapLink(FibHeap* y, FibHeap* x)
{
   removeFromRootFibHeap(y);
   addChild(x,y);
   y->mark = false;
}

void consolidate()
{
   FibHeap * A[MAX];
   for(int i=0;i<N;i++)
      A[i] = NULL;
   FibHeap *x = Min;
   do
   {
      int deg = x->degree;
      while(A[deg])
      {
         FibHeap *y = A[deg];
         bool sw = false;
         if(d[x->index] > d[y->index])
         {
            switchFibHeap(x,y);
            sw = true;
         }
         if(sw)
         {
            if(x == Min)
               Min = y;
            FibHeapLink(x,y);
            x = y;
         }
         else
         {
            if(y == Min)
               Min = x;
            FibHeapLink(y,x);
         }
         A[deg] = NULL;
         deg++;
      }
      A[deg] = x;
      x = x->right;
   }while(x!=Min);
   Min = NULL;
   for(int i=0;i<N;i++)
   {
      if(A[i]!=NULL)
         if(!Min || d[A[i]->index]<d[Min->index])
            Min = A[i];
   }
}

int extractMinFibHeap()
{
   int z = Min->index;
   FibHeap *rem = Min;
   if(Min != NULL)
   {
      FibHeap *x = Min->child;
      FibHeap *y = x;
      if(Min->right == Min)
      {
         if(x!=NULL)
         {
            do
            {
               y->father = NULL;
               y = y->right;
            }while(y!=x);
            Min = x;
         }
         else
            Min = NULL;
         rem->child = NULL;
         rem->left = NULL;
         rem->right = NULL;
      }
      else
      {
         Min = Min->right;
         if(x!=NULL)
         {
            x->left = Min->left->left;
            Min->left->left->right = x;
            do
            {
               y->father = NULL;
               y = y->right;
            }while(y->right!=x);
            y->right = Min;
            Min->left = y;
         }
         else
            removeFromRootFibHeap(rem);

         rem->child = NULL;
         rem->left = NULL;
         rem->right = NULL;

         consolidate();
      }
      FibSize--;
   }

   return z;
}

void cutFibHeap(FibHeap* x, FibHeap* y) 
{
   FibHeap* z = y->child;
   if(z!=NULL)
   {
      FibHeap* aux = z->right;
      while(aux!=z && aux!=x)
         aux = aux->right;
      if(aux == x)
      {
         if(aux->left != aux)
         {
            aux->left->right = aux->right;
            aux->right->left = aux->left;
            if(aux == y->child)
               y->child = aux->left;
         }
         else
            y->child = NULL;
         y->degree--;
         concatenate(aux);
         aux->father = NULL;
         aux->mark = false;
      }
   }
}

void cascadingCutFibHeap(FibHeap* y) 
{
   FibHeap* z = y->father;
   if(z!=NULL)
   {
      if(y->mark==false)
         y->mark = true;
      else
      {
         cutFibHeap(y,z);
         cascadingCutFibHeap(z);
      }
   }
}

void decreaseKeyFibHeap(FibHeap* x)
{
   FibHeap* y = x->father;
   if(y)
      if(d[x->index] < d[y->index])
      {
         cutFibHeap(x,y);
         cascadingCutFibHeap(y);
      }
}

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();

  T[0] = true;
  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;
   }

   createFibHeap();
   for(int i=1;i<N;i++)
      insertFibHeap(i);
//      insertHeap(i);
};

void solve()
{
   int xp;
   while(FibSize>1)
   {
//      xp = minHeap[0];
         xp = extractMinFibHeap();

      T[xp] = true;
//     removeHeap();
      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]);
            decreaseKeyFibHeap(ARB[aux->nod-1]);
         }
         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;
}