#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
#include <cctype>
using namespace std;

#ifdef INFOARENA
#define ProblemName "bellmanford"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

template <class T> void readNum(T &nr) {
	nr = 0;
	T sign = 1;
	char c;
	while (!isdigit(c = getchar()))
		(c == '-') && (sign = -1);
	do {
		nr = nr * 10 + c - '0';
	} while (isdigit(c = getchar()));
	nr *= sign;
}

struct edge {
	int toNod, weight;
};
vector< vector<edge> > G;
vector<int> dist;
int N, M;

#define INFINIT 2000000000

bool BellmanFord() {
	dist[0] = 0;
	for (int i = 1; i < N; i++)
		dist[i] = INFINIT;
	vector<char> isAvailable(N, 1);
	vector<char> aux(N);
	bool hasChanged = true;

	for (int i = 1; i < N && hasChanged; i++) {
		memset(&aux[0], 0, N);
		hasChanged = false;
		for (int j = 0; j < N; j++) {
			if (!isAvailable[j])
				continue;
			for (auto e : G[j])
			if (dist[j] + e.weight < dist[e.toNod]) {
				aux[e.toNod] = isAvailable[e.toNod];
				hasChanged = true;
				dist[e.toNod] = dist[j] + e.weight;
			}
		}
		memcpy(&isAvailable[0], &aux[0], N);
	}

	for (int j = 0; j < N; j++) {
		if (!isAvailable[j])
			continue;
		for (auto e : G[j])
		if (dist[j] + e.weight < dist[e.toNod])
			return false;
	}

	return true;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	readNum(N); readNum(M);
	G.resize(N);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		readNum(a); readNum(b); readNum(c);
		G[a - 1].push_back({ b - 1, c });
	}
	dist.resize(N);
	if (!BellmanFord())
		printf("Ciclu negativ!");
	else
	for (auto i = dist.begin() + 1; i != dist.end(); ++i)
		printf("%d ", *i);
	return 0;
}