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

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

const int maxn = 5e4 + 5;
const int oo = 0x3f3f3f3f;
vector <pair <int, int> > G[maxn];
int n, m, Dist[maxn], Cnt[maxn];

int BellmanFord(int source) {
	for (int i = 1; i <= n; i++) {
		Dist[i] = oo;
	}
	queue <int> Q;
	bitset <maxn> Vis = 0;
	Q.push(source);
	Vis[source] = true;
	Dist[source] = 0;
	while (!Q.empty()) {
		int node = Q.front();
		Vis[node] = false;
		Q.pop();
		for (vector <pair <int, int> > :: iterator it = G[node].begin(); it != G[node].end(); it++) {
			if (Dist[it->first] > Dist[node] + it->second) {
				Dist[it->first] = Dist[node] + it->second;
				if (Vis[it->first] == false) {
					Vis[it->first] = true;
					Cnt[it->first]++;
					Q.push(it->first);
					if (Cnt[it->first] >= n) {
						return 1;
					}
				}
			}
		}
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	fin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
	int cycle = BellmanFord(1);
	if (cycle == 1) {
		fout << "Ciclu Negativ!\n";
	}
	else {
		for (int i = 2; i <= n; i++) {
			fout << Dist[i] << " ";
		}
	}
	fin.close();
	fout.close();
    return 0;
}