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

using namespace std;

const int INF = 1e9;
const int NMAX = 50005;
const int MMAX = 250005;

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

struct Edge
{
    int u, v, wt;
};

Edge edges[MMAX];
int dst[NMAX];

int N, M;

int main()
{
    fin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int x, y, wt;
        fin >> x >> y >> wt;

        edges[i] = {x, y, wt};
    }

    fill(dst, dst + N + 1, INF);
    dst[1] = 0;

    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < M; j++)
        {
            int u = edges[j].u;
            int v = edges[j].v;
            int wt = edges[j].wt;

            if (dst[u] != INF && dst[u] + wt < dst[v])
                dst[v] = min(dst[v], dst[u] + wt);
        }
    }

    bool has_negative_cycle = false;
    for (int j = 0; j < M; j++)
    {
        int u = edges[j].u;
        int v = edges[j].v;
        int wt = edges[j].wt;

        if (dst[u] != INF && dst[u] + wt < dst[v])
        {
            has_negative_cycle = true;
            break;
        }
    }

    if (has_negative_cycle)
    {
        fout << "Ciclu negativ!\n";
    }
    else
    {
        for (int i = 2; i <= N; i++)
            fout << dst[i] << ' ';
    }

    return 0;
}