#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 d[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)d[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]){
			if(d[a] != INF){
				
				if(d[a]+e.d < d[e.b]){
					
					d[e.b] = d[a]+e.d;
					cnt[e.b]++;
					if(!inq[e.b]){
						qu.push(e.b);
						inq[e.b] = true;
					}
					
					if(cnt[e.b] >= n){
						negative_cycle = true;
					}
					
				}
				
			}
		}
	}
	
	if(negative_cycle){
		fout << "Ciclu negativ!";
	}else{
		for(int i = 2; i <= n; ++i){
			fout << d[i] << " ";
		}
	}
	
	return 0;
}