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

const int NMAX = 50005;
const int inf = 1<<29;

using namespace std;

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

vector <pair < int, int > > g[NMAX];

queue < int > q;

int nr[NMAX];
int d[NMAX];

int n, m;

int bellmanford(int nod){
	q.push(nod);
	d[nod] = 0;
	nr[nod]++;
	while(!q.empty()){
		nod = q.front();
		q.pop();
		for(auto i : g[nod])
			if(d[i.first] > d[nod] + i.second){
				d[i.first] = d[nod] + i.second;
				q.push(i.first);
				nr[i.first]++;
				if(nr[i.first] > n - 1)
					return -1;
			}
	}
	return 0;
}

int main(){
	fin >> n >> m;
	while(m--){
		int a, b, c;
		fin >> a >> b >> c;
		g[a].push_back({b, c});
	}
	fin.close();
	for(int i = 2; i <= n; i++)
		d[i] = inf;
	if(bellmanford(1))
		fout << "Ciclu negativ!\n";
	else{
		for(int i = 2; i <= n; i++)
			fout << d[i] << ' ';
		fout << '\n';
	}
	fout.close();
	return 0;
}