#include <iostream>
#include <vector>
#define INFINITY 1 << 30

using namespace std;

typedef struct muchie {
	int source;
	int dest;
	int cost;
} muchie;

int main() {
	
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	int n, m;
	scanf("%i%i", &n, &m);
	muchie** edges = new muchie*[m];
	for (int i = 0; i < m; i++) {
		int x, y, c;
		scanf("%i%i%i", &x, &y, &c);
		x--;
		y--;
		muchie* n = new muchie();
		n->source = x;
		n->dest = y;
		n->cost = c;
		edges[i] = n;
	}

	int* distance = new int[n];
	for (int i = 0; i < n; i++) {
		distance[i] = INFINITY;
	}
	distance[0] = 0;

	// pentru fiecare nod u incerc sa vad daca el ar putea relaxa o calea source ... v, calea devenind source ... u v
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m; j++) {
			muchie* edge = edges[j];
			if (distance[edge->source] + edge->cost < distance[edge->dest]) {
				distance[edge->dest] = distance[edge->source] + edge->cost;
			}
		}
	}

	bool cicluNegativ = false;
	for (int j = 0; j < m; j++) {
		muchie* edge = edges[j];
		if (distance[edge->source] + edge->cost < distance[edge->dest]) {
			cicluNegativ = true;
			break;
		}
	}

	if (cicluNegativ) {
		printf("Ciclu negativ!");
	}
	else {
		for (int i = 1; i < n; i++) {
			printf("%i ", distance[i]);
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}