#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#define SIZE 50005
#define INF 18446744454

using namespace std;
    ifstream f ("dijkstra.in");
    ofstream g ("dijkstra.out");

class Dijkstra
{
    int n;//nr de noduri
    int m;//nr de muchii
    int d[SIZE];//distantele de la nodul star la nodul i+1
    int viz[SIZE];
    vector<pair<int,int> > A[50005];
    vector<pair <int ,pair<int,int> > > heap;
    pair <int ,pair<int,int> >  aux;

public:
    Dijkstra();
    void citire();
    void afisare();
    void dijkstra();

};

Dijkstra::Dijkstra()
{
    n=0;
    m=0;
}

void Dijkstra::citire()
{
    int x,y,c;

    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        A[x].push_back(make_pair(y,c));
    }


}

void Dijkstra::afisare()
{
    for(int i=2;i<=n;i++)
        if(d[i]==INF)
            g<<0<<" ";
        else
            g<<d[i]<<" ";
}


void Dijkstra::dijkstra()
{
    int nr=0;
    for(int i=2;i<=n;i++)
        d[i]=INF;

    for(int i=1;i<=n;i++)
        viz[i]=0;

    d[1]=0;
    viz[1]=1;
    for(int i=0;i<A[1].size();i++)
    {
        heap.push_back(make_pair(-A[1][i].second,make_pair(1,A[1][i].first)));
        push_heap(heap.begin(),heap.end());
    }

    int  contor=1;

    while(contor<n)
    {
        pop_heap(heap.begin(),heap.end());
        aux=heap.back();
        heap.pop_back();

        int cost;
        int nod;
        int v;

        cost=aux.first;         //costul drumului dintre v si nod
        v=aux.second.first;    //nodul din care pleaca muchia
        nod=aux.second.second;// nodul in camre ajunge muchia

            if(d[nod] > d[v] -cost)
            {
                d[nod]=d[v]-cost;
                viz[nod]=1;
                contor++;
                for(int i=0;i<A[nod].size();i++)
                    if(viz[A[nod][i].first]==0)
                    {
                        heap.push_back(make_pair(-A[nod][i].second,make_pair(nod,A[nod][i].first)));
                        push_heap(heap.begin(),heap.end());
                    }
           }

    }

}

int main()
{
    Dijkstra D;
    D.citire();
    D.dijkstra();
    D.afisare();

    return 0;
}