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

void swap(long &a,long &b)
{
 long c = a;
 a = b;
 b = c;
}

long N,M;

long HS;
unsigned short Heap[50005];
unsigned short Pos[50005];
long Distante[50005];

vector<pair<int,int> *> *Muchii;

void heapify(long n)
{
 long done = 0;
 while (done == 0)
  {
   long sml = n;
   long l = sml << 1;
   long r = l + 1;
   if ((l <= HS) && (Distante[Heap[l]] < Distante[Heap[sml]]))
     {
      sml = l;
     }
   if ((r <= HS) && (Distante[Heap[r]] < Distante[Heap[sml]]))
     {
      sml = r;
     }
   if (sml != n)
     {
      swap(Heap[sml],Heap[n]);
      swap(Pos[Heap[sml]],Pos[Heap[n]]);
      n = sml;
     }
    else
     {
      done = 1;
     }
  }
}

long extrageMin(void)
{
 long res = Heap[1];

 Heap[1] = Heap[HS];
 HS -= 1;

 heapify(1);

 return res;
}

void improvenode(long n)
{
 long p = Pos[n];
 while ((p > 1) && (Distante[Heap[p >> 1]] > Distante[Heap[p]]))
  {
   swap(Heap[p >> 1],Heap[p]);
   swap(Pos[Heap[p >> 1]],Pos[Heap[p]]);
   p >>= 1;
  }
}

int main(void)
{
 long i,a,b,d;
 fstream fin("dijkstra.in",ios::in);
 fstream fout("dijkstra.out",ios::out);
 Muchii = new vector<pair<int,int> *>[50005];
 fin >> N >> M;
 for (i = 0;i < M;i += 1)
  {
   fin >> a >> b >> d;
   Muchii[a].push_back(new pair<int,int>(b,d));
  }
 for (i = 1;i <= N;i += 1)
  {
   Heap[i] = i;
   Pos[i] = i;
   Distante[i] = 60000000;
  }
 HS = N;
 Distante[1] = 0;
 for (i = 1;i <= N;i += 1)
  {
   d = extrageMin();
   for (a = 0;a < Muchii[d].size();a += 1)
    {
     if ((Distante[d] + Muchii[d][a]->second) <= Distante[Muchii[d][a]->first])
       {
        Distante[Muchii[d][a]->first] = (Distante[d] + Muchii[d][a]->second);
        improvenode(Muchii[d][a]->first);
       }
    }
  }
 for (i = 2;i <= N;i += 1)
  {
   if (Distante[i] == 60000000)
     {
      Distante[i] = 0;
     }
   fout << Distante[i] << " ";
  }
 fin.close();
 fout.close();
 return 0;
}