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

using namespace std;

void beolvas(int &n, vector<vector<pair<int, long long>>> &adj) {
    ifstream fin("bellmanford.in");
    int m;
    fin >> n >> m;
    adj.resize(n+1);
    while(m--) {
        int u, v;
        long long w;
        fin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
    }
    fin.close();
}

bool bellman_ford(int source, int n, vector<vector<pair<int, long long>>> &adj) {
    vector<long long> d(n+1, LLONG_MAX);
    d[source]=0;
    for(int i=1; i<n; i++) {
        for(int u=1; u<=n; u++) {
            for(auto v : adj[u]) {
                long long uj_tav=d[u]+v.second;
                if(d[u]!=LLONG_MAX && uj_tav<d[v.first]) {
                    d[v.first]=uj_tav;
                }
            }
        }
    }
    for(int u=1; u<=n; u++) {
        for(auto v : adj[u]) {
            long long uj_tav=d[u]+v.second;
            if(d[u]!=LLONG_MAX && uj_tav<d[v.first]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int n;
    vector<vector<pair<int, long long>>> adj;
    beolvas(n, adj);
    ofstream fout("bellmanford.out");
    if(!bellman_ford(1, n, adj)) {
        fout << "Ciclu negativ!";
    }
    return 0;
}