#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;
    vector<vector<pi>> adj(N + 1);
    while (M--)
    {
        int x, y, c;
        cin >> x >> y >> c;
        edges.push_back({x, y, c});
        adj[x].push_back({y, c});
    }

    const int source_vertex = 1;
    const int INF = 2e9;
    vector<int> dists_from_source_vertex(N + 1, INF);

    auto bellman_ford = [&]() -> void
    {
        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!";
        }
    };


    // bellman-ford "improvement"
    auto SPFA = [&]() -> void
    {
        vector<int> cnt_relaxed(N + 1);
        vector<bool> is_in_queue(N + 1, false);
        queue<int> useful_nodes;
        dists_from_source_vertex[source_vertex] = 0;
        useful_nodes.emplace(source_vertex);
        is_in_queue[source_vertex] = true;
        bool negative_cycle = false;
        while (!useful_nodes.empty() && !negative_cycle)
        {
            const int cur_vertex = useful_nodes.front();
            useful_nodes.pop();
            is_in_queue[cur_vertex] = false;

            for (const auto &anode : adj[cur_vertex])
            {
                if (dists_from_source_vertex[cur_vertex] + anode.second < dists_from_source_vertex[anode.first])
                {
                    dists_from_source_vertex[anode.first] = max(-INF, dists_from_source_vertex[cur_vertex] + anode.second);
                    if (!is_in_queue[anode.first])
                    {
                        useful_nodes.emplace(anode.first);
                        is_in_queue[anode.first] = true;
                    }
                    if (++cnt_relaxed[anode.first] == N)
                    {
                        negative_cycle = true;
                        break;
                    }
                }
            }
        }

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

    SPFA();
}