#include <fstream>
#include <vector>
#include <list>
#include <limits>

using namespace std;

struct edge
{
    int source;
    int dest;
    int cost;
};

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    int n, m;
    in >> n >> m;

    list<edge> edges;

    int x, y, c;
    for (int i = 0; i < m; ++i)
    {
        in >> x >> y >> c;
        edges.push_back({x, y, c});
    }

    constexpr int INF = 1 << 30;
    vector<int> dist(n + 1, INF);
    dist[1] = 0;
    bool changed = true;

    for (int i = 0; i < n - 1 && changed; i++)
    {
        changed = false;
        for (edge e : edges)
        {
            if (dist[e.dest] > dist[e.source] + e.cost)
            {
                dist[e.dest] = dist[e.source] + e.cost;
                changed = true;
            }
        }
    }

    bool negative_cycle = false;
    for (edge e : edges)
    {
        if (dist[e.dest] > dist[e.source] + e.cost)
        {
            negative_cycle = true;
            break;
        }
    }

    if (negative_cycle)
    {
        out << "Ciclu negativ!";
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            out << dist[i] << " ";
        }
    }

    in.close();
    out.close();
}