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

using namespace std;

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

struct muc{
	int no, va;
};

int n, m;
queue<int> qu;
vector<muc> gra[50041];

int webell[50041];
int wedate[50041];
bool weviz[50041];

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

int basca = 0;
void jimbalaya(){
	while(!qu.empty()){
		int a = qu.front();qu.pop();
		weviz[a] = 0;
		for(auto &b : gra[a]){
			int x = webell[a]+b.va;
			if(x < webell[b.no]){
				webell[b.no] = x;
				wedate[b.no]++;
				basca = max(basca, wedate[b.no]);
				if(!weviz[b.no]){
					qu.push(b.no);
					weviz[b.no] = 1;
				}
			}
		}
	}
}

int main(){
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b, va;
		fin >> a >> b >> va;
		gra[a].push_back({b, va});
	}
	upset();
	jimbalaya();
	
	if(basca == n){
		fout << "Ciclu negativ!";
	}else{
		for(int i = 2; i <= n; ++i){
			fout << webell[i] << " ";
		}
	}
	
	return 0;
}