#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define NMax 50005
#define pii pair<int,int>
#define inf 1e9
using namespace std;

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

int n,m,fv[NMax]= {0},cost[NMax];

vector <pii> vecini[NMax];
priority_queue <pii, vector<pii>, greater<pii>> pq;

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        vecini[x].push_back({c,y});
    }
    for(int i=1; i<=n; i++)
    {
       cost[i]=inf;
    }
    cost[1]=0;
    pq.push({cost[1],1});
    while(!pq.empty())
    {
        int nod;
        int val;
        do
        {
            nod=pq.top().second;
            val=pq.top().first;
            pq.pop();
        }
        while(val!=cost[nod]);
        fv[nod]++;
        if(fv[nod]==n)
        {
            fout<<"Ciclu negativ!";
            return 0;
        }
        for(auto i: vecini[nod])
        {
            cost[i.second]=min(cost[i.second],cost[nod]+val);
            pq.push({cost[i.second],i.second});

        }
    }
    return 0;
}