#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> inQueue(N, 0);
	vector<int> nUsed(N, 0);
	queue<int> Q;
	Q.push(0);
	inQueue[0] = 1;
	while (!Q.empty()) {
		int t = Q.front();
		Q.pop();
		inQueue[t] = 0;
		for (auto i : G[t])
		if (dist[t] + i.weight < dist[i.toNod]) {
			nUsed[i.toNod]++;
			if (nUsed[i.toNod] >= N)
				return false;
			dist[i.toNod] = dist[t] + i.weight;
			if (!inQueue[i.toNod]) {
				inQueue[i.toNod] = 1;
				Q.push(i.toNod);
			}
		}
	}
	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;
}