#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


const int NMax=100005;
int NHeap, N,M,D[NMax],S[NMax];
int Heap[NMax],Pos[NMax];
const int oo=2000000000;
vector < pair <int,int> >G[NMax];

void Print()
{
    for(int i=2;i<=N;++i)
        {
            if(D[i]==oo)
                D[i]=0;
            fout<<D[i]<<" ";
        }
        fout<<"\n";
    }

void Read()
{
    fin>>N>>M;

    for(int i=1;i<=M;++i)
    {
        int x,y,c;
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
}

void UpHeap(int X)
{
  int Father = X/2;
  if(Father && D[Heap[Father]] > D[Heap[X]])
  {
    swap(Heap[Father],Heap[X]);
    swap(Pos[Heap[Father]],Pos[Heap[X]]);
    UpHeap(Father);
  }
}

void DownHeap(int X)
{
  int Son1 = 2*X,Son2 = 2*X+1,Son;
  if(Son1 > NHeap)
    return;
  if(Son1 == NHeap)
  {
    if(D[Heap[Son1]] < D[Heap[X]])
      swap(Heap[Son1],Heap[X]);
      swap(Pos[Heap[Son1]],Pos[Heap[X]]);
    return;
  }
  if(D[Heap[Son1]] < D[Heap[Son2]])
    Son = Son1;
  else
    Son = Son2;
  if(D[Heap[Son]] < D[Heap[X]])
  {
    swap(Heap[Son],Heap[X]);
    swap(Pos[Heap[Son]],Pos[Heap[X]]);
    DownHeap(Son);
  }
}

void dijkstra()
{
  NHeap = N;
  for(int i=1; i<=N; ++i)
  {
      D[i]=oo;
      Heap[i] = i;
      Pos[i] = i;
  }
  D[1]=0;

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


    for(int i=0;i<(int)G[Nod].size();++i)
    {
        int Vecin=G[Nod][i].first,Cost=G[Nod][i].second;
        D[Vecin]=min(D[Vecin],D[Nod]+Cost);
        UpHeap(Pos[Vecin]);
    }
  }
}



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