#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
// #define LOCAL
#ifdef LOCAL
ifstream cin("input.txt");
ofstream cout("output2.txt");
#else
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
#endif
#define cin ::cin
#define cout ::cout


struct Edge
{
    const int node1, node2, weight;
};


int main()
{
    int N, M;
    cin >> N >> M;
    vector<Edge> edges;
    while (M--)
    {
        int x, y, c;
        cin >> x >> y >> c;
        edges.push_back({x, y, c});
    }

    const int source_vertex = 1;

    [&]() -> void
    {
        const int INF = 2e9;
        vector<int> dists_from_source_vertex(N + 1, INF);
        dists_from_source_vertex[source_vertex] = 0;
        int last_relaxed_node = -1;
        for (int i = 0; i < N; ++i)
        {
            last_relaxed_node = -1;
            for (const auto &edge : edges)
            {
                if (dists_from_source_vertex[edge.node1] == INF)
                {
                    continue;
                }
                if (dists_from_source_vertex[edge.node1] + edge.weight < dists_from_source_vertex[edge.node2])
                {
                    dists_from_source_vertex[edge.node2] = max(-INF, dists_from_source_vertex[edge.node1] + edge.weight);
                    last_relaxed_node = edge.node2;
                }
            }
        }

        if (last_relaxed_node == -1)
        {
            for (int i = 2; i <= N; ++i)
            {
                cout << dists_from_source_vertex[i] << " ";
            }
        }
        else
        {
            cout << "Ciclu negativ!";
        }
    }();
}