#include <stdio.h>
#include <vector>
#define INF 2000000000
#define H 50010

using namespace std;

long n, m, aux, a, b, c, i, j, d[H], Q[H * 20], V[H];
vector < long > G[H], C[H];

int main() {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	
	scanf("%ld %ld", &n, &m);
	for (i = 1; i <= m; ++i) {
		scanf("%ld %ld %ld", &a, &b, &c);
		G[a].push_back(b);
		C[a].push_back(c);
	}
	
	fill(d + 2, d + n + 1, INF);
	Q[++Q[0]] = 1;
	
	for (i = 1; i <= Q[0]; ++i) {
		aux = G[Q[i]].size();
		for (j = 0; j < aux; ++j)
			if (d[Q[i]] + C[Q[i]][j] < d[G[Q[i]][j]]) {
				d[G[Q[i]][j]] = d[Q[i]] + C[Q[i]][j];
				if (V[G[Q[i]][j]] < n) Q[++Q[0]] = G[Q[i]][j], ++V[G[Q[i]][j]];
				else {printf("Ciclu negativ!"); return 0;}
			}
	}
	
	//for (i = 2; i <= n; ++i) printf("%ld ", d[i]);
	return 0;
}