#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int N = 50002;
const int oo=1000000010;
int n,m,d[N];
vector<pair<int,int>> v[N];
priority_queue<pair<int,int>> pq; /// coada de prioritati tine drumuri de la 1 la un nod
/// perechea < lungime, nod > ... in varful cozii de prioritati - se tine cel mai scurt drum disponibil
/// deoarece o coada de prioritati pune mereu in varf elementul cel mai mic folosim
/// TRUC : punem distanta cu semn schimbat -> cel mai mare element este de fapr cel mai mic !!!
bitset<N> rezolvat;
int main()
{
    /// citire si formarea listelor de vecin
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        v[a].push_back(make_pair(b,c)); /// in lista vecinilor lui a se adauga nodul b cu arc de lungime c
    }
    for(int i=1;i<=n;i++)
        d[i]=oo;
    d[1]=0;
    pq.push(make_pair(0,1)); /// distanta 0 nod 1
    while(pq.size())
    {
        /// alegem cel mai scurt drum disponibil
        int dist,nod;
        tie(dist,nod)=pq.top();
        dist=-dist; /// refacem lungimea corecta a drumului
        pq.pop();/// eliminam acest drum din coada

        /// verificam daca nodul curent este rezolvat

        /// rezolvat inseamna : am setat la acel nod cel mai mic drum si
        /// am plecat apoi la vecini sa incerc sa imbunatatesc de acolo drumurile pana al vecini

        if(rezolvat[nod]==0)/// daca nodul nu a fost rezolvat
        {
            /// observatie dist = d[nod] va fi lungimea drumului minim !!!
            /// acum incercam la toti vecini sa imbunatatim distanta trcand prin acest nod
            rezolvat[nod]=1;
            for(auto it:v[nod])/// merg la toti vecinii nodului
            {
                int vec,lgArc;
                tie(vec,lgArc)=it;/// consider vecinul si lungimea arcului
                if(dist+lgArc<d[vec]) /// daca prin nod obtin un drum mai scurt folosind arcul
                {
                    d[vec]=dist+lgArc; /// setez distanta mai buna la vecin
                    pq.push(make_pair(-d[vec],vec));/// adaug acest drum pana la vecin in coada de prioritati
                    /// pun distanta cu semn schimbat ( aplic trucul care imi tine la suprafata cel mai mic element)
                }
            }
        }
    }
    /// cand coada de prioritati se goleste ... am rezolvat problema

    for(int i=2;i<=n;i++)
    {
        if(d[i]==oo)
            d[i]=0;
        g<<d[i]<<' ';
    }
    g<<'\n';

    return 0;
}

/// lungime maxima drum - cel mult 49.999 arce de lungime cel mult 20.000
/// 50.000*20.000 = 1.000.000.000