#include <fstream>
#include <iostream>
#include <queue>
#include <limits.h>
#include <utility>
#include <string.h>

#define NMAX 50004
#define INF (LLONG_MAX - 2000)

typedef std::pair<int, int> Link;
typedef std::pair<Link, int> Edge;
typedef std::vector<Edge> EdgeContainer;
long long d[NMAX];

EdgeContainer neighbors;

int main () {
	std::ifstream fin("bellmanford.in");
	std::ofstream fout("bellmanford.out");

	int n, m, x, y, cost, i;
	fin >> n >> m;

	for (i = 2; i <= n; i++) {
		d[i] = INF;
	}

	for (i = 1; i <= m; i++) {
		fin >> x >> y >> cost;
		neighbors.push_back(Edge(Link(x, y), cost));
		if (x == 1) {
			d[y] = cost;
		}
	}

	d[1] = 0;
	bool stop = false;

	for (i = 1; i <= n - 2 && !stop; i++) {
		stop = true;
		for (EdgeContainer::iterator it = neighbors.begin();
			it != neighbors.end(); it++) {

			x = (it->first).first;
			y = (it->first).second;
			if (d[y] > d[x] + it->second) {
				stop = false;
				// std::cout << '('<< y << ", "<< d[y] << ", ";
				d[y] = d[x] + it->second;
				// std::cout << d[y] <<"), ";
			}
		}
			// std::cout << "\n";
	}

	for (EdgeContainer::iterator it = neighbors.begin();
		it != neighbors.end() && !stop; it++) {

		x = (it->first).first;
		y = (it->first).second;
		if (d[y] > d[x] + it->second) {
			fout << "Ciclu negativ!\n";
			return 0;
		}
	}

	for (i = 2; i <= n; i++) {
		if (d[i] == INF) {
			fout << "0 ";
		} else {
			fout << d[i] << ' ';
		}
	}
	fout << "\n";

	return 0;
}