#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;
vector<vector<pair<int,int>>> mat(nmax);
vector<int> distante(nmax);
void read_input(){
	fin >> n >> m;
	int nod_1,nod_2,cost;
	for(int i = 1; i <=m; i++){
		fin >> nod_1 >> nod_2 >> cost;
		mat[nod_1].push_back(make_pair(nod_2,cost));
	}
};
void bellman_ford(){
	fill(distante.begin(),distante.end(),inf);
	distante[1] = 0;
	for(int i = 1; i <=n; i++){
		for(int nod = 1; nod <=n; nod++){
			for(auto nod_aux : mat[nod]){
				if(distante[nod_aux.first] > distante[nod] + nod_aux.second){
					distante[nod_aux.first] = distante[nod] + nod_aux.second;
				}
			}
		}
	};
	int exista_ciclu = 0;
	for(int nod = 1; nod <=n && !exista_ciclu; nod++){
			for(auto nod_aux : mat[nod]){
				if(distante[nod_aux.first] > distante[nod] + nod_aux.second){
					exista_ciclu = 1;
				}
			}
		};
	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;
}