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

struct muc{
	int dest, cost; };

int main(){
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	int n, m;
	f >> n >> m;
	vector<vector<muc> > graf(n);
	vector<int> dist(n, 1000000000);
	dist[0] = 0;
	for(int i = 0, a, b, c; i < m; ++i){
		f >> a >> b >> c;
		--a, --b;
		graf[a].push_back({b, c}); }
	queue<int> de_viz;
	vector<bool> in_queue(n, false);
	vector<int> cnt_in_queue(n, 0);
	de_viz.push(0), in_queue[0] = true, cnt_in_queue[0] = 0;
	bool ciclu_negativ = false;
	while(!de_viz.empty() && !ciclu_negativ){
		const int cur = de_viz.front();
		de_viz.pop();
		in_queue[cur] = false;
		for(const auto next : graf[cur]){
			if(dist[next.dest] > dist[cur] + next.cost){
				dist[next.dest] = dist[cur] + next.cost;
				if(!in_queue[next.dest]){
					if(cnt_in_queue[next.dest] > n){
						ciclu_negativ = true; }
					else{
						++cnt_in_queue[next.dest];
						in_queue[next.dest] = true;
						de_viz.push(next.dest); } } } } }

	for(int i = 0; i < n && !ciclu_negativ; ++i){
		for(const auto next : graf[i]){
			if(dist[next.dest] > dist[i] + next.cost){
				ciclu_negativ = true; } } }
	if(ciclu_negativ){
		g << "Ciclu negativ!"; }
	else{
		for(int i = 1; i < n; ++i){
			g << dist[i] << ' '; } }
	
	return 0; }