#include <iostream>
#include <queue>
#include <fstream>
#include <vector>

using namespace std;

#define MAX_N 50005

const int INF = 10000000;

struct muchie
{
    int c, x, y;
};

int d[MAX_N];

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    vector<muchie> muchii;
    int n, m, x, y, c, i;
    bool ciclunegativ = false;

    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        muchii.push_back({c, x, y});
    }

    for (i = 1; i <= n; i++)
        d[i] = INF;

    d[1] = 0;


    for (int i = 1; i <= n; i++)
    {
        for (muchie m : muchii)
        {
            int x = m.x;
            int y = m.y;
            int cost = m.c;

            if (d[x] < INF && d[y] > d[x] + cost)
            {
                if (i < n)
                {
                   d[y] = d[x] + cost;
                }
                else
                {
                    ciclunegativ = true;
                    break;
                }
            }
        }
    }

    if (ciclunegativ)
        g << "Ciclu negativ!\n";
    else
        for (i = 2; i <= n; i++)
        {
            if (d[i] != INF)
                g << d[i] << ' ';
            else
                g << 0 << ' ';
        }

    return 0;
}