#include <bits/stdc++.h>
#define inf 1 << 30
#define nmax 50005
#define mmax 250005

using namespace std;

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

int vertices, edges;
int d[nmax];
pair<pair<int, int>, int> edge[mmax];

int main()
{
    fin >> vertices >> edges;
    for(int i = 1; i <= edges; ++i)
    {
        fin >> edge[i].first.first >> edge[i].first.second >> edge[i].second;
    }
    for(int i = 1; i <= vertices; ++i) d[i] = inf;
    d[1] = 0;
    for(int i = 1; i < vertices; ++i)
    {
        for(int i = 1; i <= edges; ++i)
        {
            if(d[edge[i].first.first] + edge[i].second < d[edge[i].first.second])
            {
                d[edge[i].first.second] = d[edge[i].first.first] + edge[i].second;
            }
        }
    }
    for(int i = 1; i < vertices; ++i)
    {
        for(int i = 1; i <= edges; ++i)
        {
            if(d[edge[i].first.first] + edge[i].second < d[edge[i].first.second])
            {
                d[edge[i].first.second] = -inf;
                fout << "Ciclu negativ!";
                return 0;
            }
        }
    }
    for(int i = 2; i <= vertices; ++i)
        fout << d[i] << " ";
    return 0;
}