#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 10000
#define INF (1 << 30)
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,c;
bool viz[NMAX];
int distanta[NMAX];

//functia de comparare pe care o folosim in coada
struct comp
{
    bool operator()(int x,int y)
    {
        return distanta[x]>distanta[y];
    }

};
//folosim o coada priority pentru a putea accesa distanta minima a nodului
priority_queue< int, vector<int>, comp> coada;//vector<int> este structura in care adunam toate obiectele
vector<pair<int,int> > vecini[NMAX];
void Dijkstra(int s)
{
    int s2;
    //distanta nodului de inceput este 0 ,nu exista distanta de la el la el insusi
    distanta[s]=0;
    //il punem in coada
    viz[s]=1;
    coada.push(s);
    while(!coada.empty())
    {
        //extragem nodul curent(este mereu nodul minim)
        s2=coada.top();
        viz[s2]=0;
        //eliminam nodul curent
        coada.pop();
        //parcurgem vecini nodului curent
        for(unsigned int i=0; i<vecini[s2].size(); i++)
        {
            //s3 va memora nodul vecin(y),iar cost stocheaza costul muchiei [s2-s3]
            int s3=vecini[s2][i].first;
            int cost=vecini[s2][i].second;
            //daca suma dintre distanta de la nodul curent si costul muchiei noastre este mai mica decat distanta calculata pana atunci
            if(distanta[s2]+cost<distanta[s3])
            {
                //actualizam costul
                distanta[s3]=distanta[s2]+cost;
                if(viz[s3]==0)
                {
                    viz[s3]=1;
                    coada.push(s3);


                }
            }

        }
    }


}
int main()
{
    f>>n>>m;

    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        //punem in vecini[x] toti vecini y care au cost c;
        vecini[x].push_back(make_pair(y,c));

    }
    //initializam vectorul de distante cu valoare INF
    for (int i=1; i<=n; i++)
    {
        distanta[i]=INF;
    }
    Dijkstra(1);
//afisam elementele vectorului distanta
    for(int i=2; i<=n; i++)
    {
        if(distanta[i]!=INF)
            g<<distanta[i]<<" ";
        else
            g<<"0";
    }



    return 0;
}