#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

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

const int INF = 0x3f3f3f3f;

struct edg{
	int b, d;
};

int n, m;
vector<edg> gra[50041];

queue<int> qu;
bool inq[50041];
int cnt[50041];

int dst[50041];

int main(){
	// ios_base::sync_with_stdio(false);
	
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b, d;
		fin >> a >> b >> d;
		gra[a].push_back({b, d});
	}
	
	for(int i = 2; i <= n; ++i)dst[i] = INF;
	
	bool negative_cycle = false;
	
	qu.push(1);
	while(!qu.empty() && !negative_cycle){
		int a = qu.front();
		qu.pop();
		inq[a] = false;
		
		for(auto e : gra[a]){
			int b = e.b;
			int d = e.d;
			
			if(dst[a] == INF)continue;
			
			if(dst[a]+d < dst[b]){
				dst[b] = dst[a]+d;
				cnt[b]++;
				if(!inq[b]){
					qu.push(b);
					inq[b] = true;
				}
				
				if(cnt[b] >= n){
					negative_cycle = true;
				}
			}
		}
	}
	
	if(negative_cycle){
		fout << "Ciclu negativ!";
	}else{
		for(int i = 2; i <= n; ++i){
			fout << dst[i] << " ";
		}
	}
	
	return 0;
}