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

using namespace std;

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

struct muc{
	int b, v;
};
vector<muc> gra[50041];

int n, m;
int dis[50041], amt[50041];
bool vi[50041];
queue<int> qu;

void init(){
	for(int i = 2; i <= n; ++i){
		dis[i] = INT_MAX;
	}
	qu.push(1);
	vi[1] = 1;
}

bool fordy(){
	int yo = 0;
	init();
	while(!qu.empty() && yo < n){
		int a = qu.front();qu.pop();
		vi[a] = 0;
		for(auto w : gra[a]){
			int x = dis[a]+w.v;
			if(x < dis[w.b]){
				amt[w.b]++;
				yo = max(yo, amt[w.b]);
				dis[w.b] = x;
				if(!vi[w.b]){
					vi[w.b] = 1;
					qu.push(w.b);
				}
			}
		}
	}
	return yo<n;
}

int main(){
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		muc w;
		int a;
		fin >> a >> w.b >> w.v;
		gra[a].push_back(w);
	}
	
	if(fordy()){
		for(int i = 2; i <= n; ++i){
			fout << dis[i] << " ";
		}
	}else{
		fout << "Ciclu negativ!";
	}
	return 0;
}