#include <fstream>
#include <algorithm>
#include <vector>
#define oo 1<<30
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int NHeap, N,M,L[50005],Heap[50005],Poz[50005];
vector <pair <int,int> > G[50005];
void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int s,f,d;
        fin>>s>>f>>d;
        G[s].push_back(make_pair(f,d));
    }
}

void UpHeap(int Node)
{
  int Father = Node / 2;
  if(Father > 0 && L[Heap[Father]] > L[Heap[Node]])
    {
      swap(Heap[Father],Heap[Node]);
      swap(Poz[Father],Poz[Node]);
      UpHeap(Father);
    }
}

void DownHeap(int Node)
{
  int Son1 = 2 * Node, Son2 = 2 * Node + 1;
  if(Son1 > NHeap)
    return;
  if(Son1 == NHeap)
    {
      if(L[Heap[Son1]] < L[Heap[Node]])
        {
          swap(Heap[Son1],Heap[Node]);
          swap(Poz[Son1],Poz[Node]);
          return;
        }
    }
  if(L[Heap[Son1]] < L[Heap[Son2]])
    {
     if(L[Heap[Son1]] < L[Heap[Node]])
        {
          swap(Heap[Son1],Heap[Node]);
          swap(Poz[Son1],Poz[Node]);
          DownHeap(Son1);
        }
    }
  else
     {
     if(L[Heap[Son2]] < L[Heap[Node]])
        {
          swap(Heap[Son2],Heap[Node]);
          swap(Poz[Son2],Poz[Node]);
          DownHeap(Son2);
        }
    }
}

void Dijkstra()
{
    for(int i=1;i<=N;i++)
    {
        L[i]=oo;
        Heap[i] = i;
        Poz[i] = i;
    }
    L[1] = 0;
    NHeap = N;

    for(int k = 1;k <= N; ++k)
    {
        int Nod = Heap[1];
        Heap[1] = Heap[NHeap--];
        DownHeap(1);

        for(int i = 0; i < (int)G[Nod].size(); ++i)
        {
            int Vecin=G[Nod][i].first,Cost=G[Nod][i].second;
            if(L[Nod] + Cost < L[Vecin])
              {
                L[Vecin] = L[Nod] + Cost;
                UpHeap(Poz[Vecin]);
              }
        }
    }
}
void Print()
{
    for(int i=2;i<=N;i++)
    {
        if(L[i]==oo) L[i]=0;
        fout<<L[i]<<" ";
    }
}

int main()
{
    Read();
    Dijkstra();
    Print();
    return 0;
}