#include <bits/stdc++.h>
#define NM 50000
using namespace std;
const int inf=0xffffffff;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int cst[NM],fcv[NM];
//vector costuri, vector frecventa

queue <int> q;//coada evidenta noduri tata
vector <pair<int,int>>v[NM]; //lista adiacenta + cost

int main()
{ int n,m,x,y,c;
    f>>n>>m;
   //cin>>n>>m;


 //citesc in ordine valorile si in v[x](nodul tata) se adauga perechile (nod(fiu), cst) in liste de adiacenta
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        //cin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }


// adaug in coada nodul de inceput-1
   q.push(1);

//setez cu inf vectorul de costuri
    for(int i=2;i<=n;++i)
        cst[i]=inf;


    while(!q.empty())
    {
        x=q.front();
        q.pop();//il scoatem cand relaxam muchiile aferente lui
        for(int i=0;i<v[x].size();++i)
        {
             y=v[x][i].first;
            if(cst[y]>cst[x]+v[x][i].second)
            {

// pt fiecare vecin al nodului curent se actualizeaza costul minim
                cst[y]=cst[x]+v[x][i].second;
                q.push(y);
                fcv[y]++;
//nu există cicluri negative ⇔ nu se mai fac actualizări la pasul n

                if(fcv[y]>=n)
                 {  g<<"Ciclu negativ!";
                    //cout<<"ciclu negativ";
                }

            }
        }
    }
    // Afisare daca nu exista costuri negative
    for(int i=2;i<=n;++i)
        {  g<<cst[i]<<" ";
           //cout<<cst[i]<<" ";
        }

    return 0;
}