#include <fstream>
#include <vector>
#define oo 2000000000
#define NMax 50000
using namespace std;
int N,M;
vector <pair <int, int> >G[NMax];
int D[NMax];
int Heap[NMax],Poz[NMax],NHeap;
void Read()
{
    ifstream in ("dijkstra.in");
    in>>N>>M;
    for (int i=0;i<M;i++)
    {
        int A,B,C;
        in>>A>>B>>C;
        G[A].push_back(make_pair(B,C));
    }
    in.close();
}

void Swap(int Nod, int Tata)
{
    swap(Heap[Nod],Heap[Tata]);
    swap(Poz[Heap[Nod]],Poz[Heap[Tata]]);
}

void UpHeap(int Nod)
{
    int Tata = Nod / 2;

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

void DownHeap(int Nod)
{
    int Son = 2*Nod;

    if(Son > NHeap)
        return;

    if(Son == NHeap && D[Heap[Son]] < D[Heap[Nod]])
        {
            Swap(Son,Nod);
            return;
        }

    if(D[Heap[Son]] < D[Heap[Son+1]])
        {
            if(D[Heap[Son]] < D[Heap[Nod]])
                {
                    Swap(Son, Nod);
                    DownHeap(Son);
                }
        }
    else
        {
            if(D[Heap[Son+1]] < D[Heap[Nod]])
                {
                    Swap(Son+1, Nod);
                    DownHeap(Son+1);
                }
        }
}


void Solve()
{
    int Nod;
    int Cost;
    for (int i= 1;i<=N;i++)
        D[i]=oo;
    D[1]=0;

    for(int i = 1; i<=N; i++)
        {
            Heap[i] = i;
            Poz[i] = i;
        }
    NHeap = N;

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

        //Relaxarea Vecinilor (imbunatatirea costului vecinilor)
        for (int j=0;j < (int)G[Nod].size();j++)
        {
            int Vecin=G[Nod][j].first;
            Cost=G[Nod][j].second;
            if(D[Nod] + Cost < D[Vecin])
                {
                    D[Vecin] = D[Nod] + Cost;
                    UpHeap(Poz[Vecin]);
                }

        }
    }
}
void Write()
{
    ofstream fout ("dijkstra.out");
    for (int i = 2;i <= N; ++i)
    {
        if (D[i]!=oo)
            fout<<D[i]<<' ';
        else
            fout<<0<<' ';
    }
}
int main()
{
    Read();
    Solve();
    Write();
    return 0;
}