#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct edge{
	int u, v, cost;
};
const int infinit = 1000000;

struct edge edges[250005];
int d[50005];

int main() {
	int n, m,i, j, v, u, cost;
	f >> n >> m;	
	for(i = 1; i <= m; ++i) {
		f >> edges[i].u >> edges[i].v >> edges[i].cost;
	}
	for(i = 1; i <= n; ++i) {
		d[i] = infinit;
	}
	d[1] = 0;
	for(i = 1; i <= n; ++i) {
		for(j = 1; j <= m; ++j) {
				u = edges[j].u;
				v = edges[j].v;
				cost = edges[j].cost;
				d[v] = min(d[v], d[u] + cost);
		}
	}
	bool ciclu_negativ = false;
	for(j = 1; j <= m; ++j) {
			u = edges[j].u;
			v = edges[j].v;
			cost = edges[j].cost;
			if(d[v] < d[u] + cost){
				ciclu_negativ = true;
			}
	}
	if(ciclu_negativ) {
		g << "Ciclu negativ!";
	} else {
		for(i = 1; i <= n; ++i) {
			g << d[i] << " ";
		}
	}
}