#include <iostream>
#include <fstream>
using namespace std;
ifstream ka("bellmanford.in");
ofstream ki("bellmanford.out");
const int N_MAX = 50000;
const int M_MAX = 250000;
int n, m, x, y, c, distanta[N_MAX + 1];
struct muchie
{
    int x, y, c;
}muchii[M_MAX + 1];

int main()
{
    ka >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        muchie muchie;
        ka >> muchie.x >> muchie.y >> muchie.c;
        muchii[i] = muchie;
    }
    distanta[1] = 0;
    for(int i = 2; i <= n; i++)
        distanta[i] = 0x7fffffff;

    bool schimbat = true;
    for(int i = 1; i <= n && schimbat; i++)
    {
        schimbat = false;
        for(int j = 1; j <= m; j++)
        {
            if(distanta[muchii[j].x] + muchii[j].c < distanta[muchii[j].y])
            {
                distanta[muchii[j].y] = distanta[muchii[j].x] + muchii[j].c;
                schimbat = true;
            }
        }
    }
        ki << "Ciclu negativ!\n";
}