#include <bits/stdc++.h>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int N = 50002;
const int oo=1000000010;
int n,m,d[N],cnt[N];
vector<pair<int,int>> v[N];
queue<int> q; /// coada cu noduri in care s-a imbunatatit solutia
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;
    q.push(1); /// am in coada, deocamdata, nodul de plecare
    while(q.size())
    {
        int nod=q.front(); /// luam un nod care a fost imbunatatit
        q.pop(); /// si il eliminam din coada

        for(auto it:v[nod])/// merg la toti vecinii nodului
        {
                int vec,lgArc;
                tie(vec,lgArc)=it;/// consider vecinul si lungimea arcului
                if(d[nod]+lgArc<d[vec]) /// daca prin nod obtin un drum mai scurt folosind arcul
                {
//                    cnt[vec]++;
//                    if(cnt[vec]==n)
//                    {
//                        g<<"Ciclu negativ!\n";
//                        return 0;
//                    }
//                    d[vec]=d[nod]+lgArc; /// setez distanta mai buna la vecin
                    q.push(vec);/// adaug acest vecin in coada
                }
        }
    }
    /// cand coada de prioritati se ... am rezolvat problema
    /// faptul ca graful este "conex" vrea sa spuna de fapt ca mereu pot ajunge din 1 in oricare
    /// alt nod
    for(int i=2;i<=n;i++)
        g<<d[i]<<' ';
    g<<'\n';

    return 0;
}