#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

const int N_MAX = 50001;
const int M_MAX = 250001;
const int POSITIVE_INFINITY = (1 << 30) - 1;
const int NEGATIVE_INFINITY = -(1 << 30);

struct Vertex
{
    int at, to, cost;
}Vertices[M_MAX];

int n, m;
int dist[N_MAX];
bool x = false;

void Read()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> Vertices[i].at >> Vertices[i].to >> Vertices[i].cost;
    }
}

void BellmanFord(int startNode)
{
    for (int i = 1; i <= n; i++)
    {
        dist[i] = POSITIVE_INFINITY;
    }
    dist[startNode] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (dist[Vertices[j].at] + Vertices[j].cost < dist[Vertices[j].to])
            {
                dist[Vertices[j].to] = dist[Vertices[j].at] + Vertices[j].cost;
            }
        }
    }

    for (int i = 1; i <= m; i++)
    {
        if (dist[Vertices[i].at] + Vertices[i].cost < dist[Vertices[i].to])
        {
            dist[Vertices[i].to] = NEGATIVE_INFINITY;
            x = true;
        }
    }
}

int main()
{
    Read();
    BellmanFord(1);
    if (x == true)
    for (int i = 1; i <= n; i++)
    {
        g << dist[i] << " ";
    }
    else
    {
        g << "Ciclu negativ!";
    }
}