#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

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

int n, m, x, y, c, cnt[50100], d[50100];
vector <pair <int, int> > v[50100];
queue <pair <int, int> > q;

int main(){
	in >> n >> m;
	while(m--){
		in >> x >> y >> c;
		v[x].push_back({y, c});
	}
	for(int i = 2; i <= n; i++)
		d[i] = 2e9;
	q.push({1, 0});
	while(q.size()){
		auto w = q.front();
		q.pop();
		for(auto x : v[w.fi]){
			if(w.se + x.se < d[x.fi]){
				d[x.fi] = w.se + x.se;
				cnt[x.fi]++;
				q.push({x.fi, d[x.fi]});
				if(cnt[x.fi] == n)
					return out << "Ciclu negativ!", 0;
			}
		}
	}
	for(int i = 2; i <= n; i++)
		out << d[i] << ' ';
	return 0;
}