#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct muchie
{
    int x,y,val;
};
int main()
{
    int n,m;
    fin>>n>>m;
    int d[n+1];
    for(int i=2; i<=n; i++)
        d[i]=INT_MAX;
    d[1]=0;
    vector<muchie> muchii;
    while(m--)
    {
        muchie m;
        fin>>m.x>>m.y>>m.val;
        muchii.push_back(m);
    }
    for(int i=1; i<n; i++)
    {
        for(auto m:muchii)
        {
            if(d[m.x] != INT_MAX && d[m.x] + m.val<d[m.y])
                d[m.y] = d[m.x] + m.val;
        }
    }

    for(auto m:muchii)
    {
        if(d[m.x] != INT_MAX && d[m.x] + m.val<d[m.y])
            {fout<<"Ciclu negativ!";return 0;}

    }

    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";

    return 0;
}