#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

const int M = 50000;

ifstream fcin("bellmanford.in");
ofstream fcout("belmmanford.out");

struct edge
{
    int s, d, c;
};

struct graph
{
    int n, m;
    edge x[M];
} g;

int D[M], menet;
bool vege;

int vegtelen()
{
    int sum = 0;
    for (int i = 0; i < g.m; ++i)
        sum += abs(g.x[i].c);
    return sum + 1;
}

bool bellmanFord()
{
    int inf = vegtelen();
    for (int i = 0; i <= g.n; ++i)
        D[i] = inf;
    D[1] = 0;

    for (; menet < g.n && !vege; ++menet)
    {
        vege = true;
        for (int i = 0; i < g.m; ++i)
            if (g.x[i].c + D[g.x[i].s] < D[g.x[i].d])
            {
                D[g.x[i].d] = g.x[i].c + D[g.x[i].s];
                vege = false;
            }
    }
    if (menet >= g.n)
        return false;
    return true;
}

int main()
{
    fcin >> g.n >> g.m;
    for (int i = 0; i < g.m; ++i)
        fcin >> g.x[i].s >> g.x[i].d >> g.x[i].c;

    if (bellmanFord())
        for (int i = 2; i <= g.n; ++i)
            fcout << D[i] << ' ';
    else
        fcout << "Ciclu negativ!";
}