#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int N = 50002;
const int oo = 1000000010;
int d[N];/// sirul solutie ( distantelor )
vector<pair<int,int>> v[N];/// listele de vecini : perechi cost,vecin
priority_queue<pair<int,int>> pq; /// coada de prioritati a nodurilor dupa cost : perechi -cost,vecin
/// in pq se pune -cost in loc de cost astfel incat cel mai mic cost sa devina cel mai mare (-cost)
int n,m;
int main()
{
    /// citirea grafului
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int nod,vec,cost;
        f>>nod>>vec>>cost;
        v[nod].push_back(make_pair(cost,vec));
    }
    /// initializarea costurilor si a cozii de prioritati

    for(int i=2;i<=n;i++)/// in nodul sursa 1 plec cu costul 0
        d[i]=oo;
    pq.push(make_pair(0,1));

    /// procesarea in ordinea crescatoare a costurilor
    while(pq.size())
    {
        int nod,costNod;
        tie(costNod,nod)=pq.top(); /// imi iau nodul cu costul minim
        costNod=-costNod;/// "repar" costul
        pq.pop();
        /// este posibil ca un nod sa fie imbunatatit de mai multe ori
        /// de procesat va fi procesat o singura data
        /// ulterior va iesi din coada cu costuri mai proaste obtinute
        /// inainte ca costul sa devina optim !!!

        /// nu procesez un nod care deja a fost optimizat !!!
        if(costNod!=d[nod])
            continue;

        for(auto it:v[nod])
        {
            int vec,costMuchie;
            tie(costMuchie,vec)=it; /// imi iau fiecare muchie din nod spre un vecin

            /// daca drumul pana in vec prin aceasta muchie imbunatateste
            /// costul la vecin, aplic imbunatatirea !!!
            if(costNod+costMuchie<d[vec])
            {
                d[vec]=costNod+costMuchie;
                pq.push(make_pair(-d[vec],vec)); /// cand pun in pq nu uit sa schimb semnul la cost
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==oo)
            d[i]=0;
        g<<d[i]<<' ';
    }
    return 0;
}