#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

#ifdef LOCAL
#define fin cin
#define fout cout
#else
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#endif

vector<pair<int, int>> adj[50001];
vector<int> d(50001, 2e9);
queue<int> q;
int frecv[50001];

int main() {
	int n, m, x, y, c;
	fin >> n >> m;
	while (m--) {
		fin >> x >> y >> c;
		adj[x].push_back({y, c});
	}
	q.push(1);
	d[1] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		frecv[u]++;
		if (frecv[u] == n) {
			fout << "Ciclu negativ!";
			return 0;
		}
		for (auto v:adj[u]) {
			if (d[v.first] > d[u] + v.second) {
				d[v.first] = d[u] + v.second;
				q.push(v.first);
			}
		}
	}
	for (int i=2; i<=n; i++) fout << d[i] << ' ';
}