#include <iostream>
#include <fstream>
#include <deque>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>

#define MAXN 50010
#define MAXM 250010
#define INF 1000000000

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct muchie {
	long a, b, c;
} e[MAXM];

long n, m, k, left, right, cost[MAXN], f[MAXN];

vector<long> v[MAXN];
vector<pair<long, long>> h;

void init() {
	cost[1] = 0;
	for (long i = 2; i <= n; ++i)
		cost[i] = INF;
	h.push_back(make_pair(0, 1));
	make_heap(h.begin(), h.end());
}

void solve() {
	pair<long, long> per;
	long i, j, nod, poz;
	long long pas = 0;

	while (h.size() && pas <= 1LL * n * m) {
		pas++;
		pop_heap(h.begin(), h.end());
		per = h.back();
		h.pop_back();
		nod = per.second;
		f[nod] = 0;

		for (j = 0; j < v[nod].size(); ++j) {
			poz = v[nod][j];
			if (cost[e[poz].a] + e[poz].c < cost[e[poz].b]) {
				cost[e[poz].b] = cost[e[poz].a] + e[poz].c;
				if (!f[e[poz].b]) {
					f[e[poz].b] = 1;
					h.push_back(make_pair(-cost[e[poz].b], e[poz].b));
					push_heap(h.begin(), h.end());
				}
			}
		}
	}

}

long check_negativ() {
	long i;
	for (i = 1; i <= m; ++i)
		if (cost[e[i].a] + e[i].c < cost[e[i].b])
			return 1;
	return 0;
}

int main() {
	fin >> n >> m;
	for (long i = 1; i <= m; ++i) {
		fin >> e[i].a >> e[i].b >> e[i].c;
		v[e[i].a].push_back(i);
	}

	init();
	solve();

	if (check_negativ()) {
		fout << "Ciclu negativ\n";
		return 0;
	}

	for (long i = 2; i <= n; ++i)
		fout << cost[i] << " ";

	return 0;
}