#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <functional>
#include <set>
#define NMAX 1004
#define endl '\n';

using namespace std;

const int INF = 1e9;
const string FL = "bellmanford";
ifstream fin(FL + ".in");
ofstream fout(FL + ".out");

int n, m;

struct Muchie {
	int u, v, cost;
};

vector<Muchie> muchii;
bool circuitNegativ = false, ok = true;
int viz[50005];

vector<int> bellmanford(int start) {
	vector<int> d(n + 1, INF);
	d[start] = 0;

	for (int i = 1; i < n; ++i) {
		if (!ok) break;
		ok = false;
		for (auto& m : muchii) {
			if (viz[m.u] == i - 1)
				if (d[m.u] != INF && d[m.v] > d[m.u] + m.cost) {
					d[m.v] = d[m.u] + m.cost;
					viz[m.v] = i;
					//tata[m.v] = m.u;
					ok = true;
				}
		}
	}
	for (auto& m : muchii) 
		if (d[m.u] != INF && d[m.v] > d[m.u] + m.cost) 
			circuitNegativ = true;
			
	return d;
}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int n1, n2, c;
		fin >> n1 >> n2 >> c;
		muchii.push_back({ n1, n2, c });
	}

	//vector<int> tata(n + 1, 0);
	vector<int> dist = bellmanford(1);

	if (circuitNegativ)
		fout << "Ciclu negativ!";
	else
		for (int i=2; i<=n; ++i)
			fout << dist[i] << " ";
	return 0;
}