#include <bits/stdc++.h>


using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

const int Nmax = 5e4 + 5;

int n , m , d[Nmax] , ap[Nmax];

vector < pair < int , int > > L[Nmax];

queue < int > Q;

bool viz[Nmax];

int main()
{
    int x , y , c;
    bool ok = false;
    fin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back({y , c});
    }
    for(int i = 1 ; i <= n ; i++)
        d[i] = 1e9;
    viz[1] = true;
    ap[1] = 1;
    Q.push(1);
    d[1] = 0;
    while(!Q.empty() && !ok)
    {
        x = Q.front();
        Q.pop();
        viz[x] = false;
        for(auto it : L[x])
            if(d[it.first] > d[x] + it.second)
        {
            d[it.first] = d[x] + it.second;
            if(!viz[it.first])
            {
                viz[it.first] = true;
                Q.push(it.first);
                ++ap[it.first];
                if(ap[it.first] == n)
                    ok = true;
            }
        }
    }
    if(ok)
        fout << "Ciclu negativ\n";
    else
    {
        for(int i = 2 ; i <= n ; i++)
            fout << d[i] << " ";
        fout << "\n";
    }
    fin.close();
    fout.close();
}