#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nmax = 5e4;
const int inf = 0x3F3F3F3F;
int n,m;
struct muchie{
	int nod_1,nod_2,cost;
};
vector<muchie> mat(nmax*5);
vector<int> distante(nmax);
void read_input(){
	fin >> n >> m;
	for(int i = 1; i <=m; i++){
		fin >> mat[i].nod_1 >> mat[i].nod_2 >> mat[i].cost;
	}
};
void bellman_ford(){
	fill(distante.begin(),distante.end(),inf);
	distante[1] = 0;
	for(int i = 1; i <=n; i++){
	    int ok = 0;
		for(auto edge : mat){
			if(distante[edge.nod_2] > distante[edge.nod_1] + edge.cost){
				distante[edge.nod_2] = distante[edge.nod_1] + edge.cost;
				ok = 1;
			}
		};
		if(!ok){break;}
	};
	int exista_ciclu = 0;
	for(auto edge : mat){
		if(distante[edge.nod_2] > distante[edge.nod_1] + edge.cost){
			exista_ciclu = 1;
			break;
		}
	}
	if(exista_ciclu){
		fout << "Ciclu negativ!";
	}else{
		for(int i = 2; i <=n; i++){
			fout << distante[i] << " ";
		}
	}	
}
int main(){
	read_input();
	bellman_ford();
	return 0;
}