#include<fstream>
#include<vector>
#define oo 1<<30
#define NMax 50005
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N,M,NHeap;
int D[NMax],Heap[NMax],Poz[NMax];

vector < pair <int,int> > G[NMax];

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 Nod)
{
    int Tata = Nod / 2;

    if(Tata > 0 && D[Heap[Tata]] > D[Heap[Nod]])
    {
        swap(Heap[Tata],Heap[Nod]);
        swap(Poz[Heap[Tata]],Poz[Heap[Nod]]);
        UpHeap(Tata);
    }
}

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

void Solve()
{
    for(int i = 1 ; i <= N ; ++i)
    {
        D[i] = oo;
        Heap[i] = i;
        Poz[i] = i;
    }

    D[1] = 0;
    NHeap = N;

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

        swap(Poz[Heap[1]],Poz[Heap[NHeap]]);
        Heap[1] = Heap[NHeap];
        NHeap--;
        DownHeap(1);

        for(int i = 0 ; i < (int) G[Nod].size() ; ++i)
        {
            int Vecin = G[Nod][i].first;
            int Cost = G[Nod][i].second;

            if(D[Nod] + Cost < D[Vecin])
            {
                D[Vecin] = D[Nod] + Cost;
                UpHeap(Poz[Vecin]);
            }
        }
    }
}

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

int main()
{
    Read();
    Solve();
    Print();

    fin.close();
    fout.close();
    return 0;
}