#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;
long Heap[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]);
      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)
{
 while ((n > 1) && (Distante[Heap[n >> 1]] > Distante[Heap[n]]))
  {
   swap(Heap[n >> 1],Heap[n]);
   n >>= 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;
   Distante[i] = 0X7FFFFFFF;
  }
 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)
  {
   fout << Distante[i] << " ";
  }
 fin.close();
 fout.close();
 return 0;
}