#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y, c, nod, dist, son, sondist, d[50100], seen[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 = 1; i <= n; i++)
		d[i] = 2e9;
	q.push({1, 0});
	while(!q.empty()){
		nod = q.front().first;
		dist = q.front().second;
		q.pop();
		if(dist > d[nod])
			continue;
		for(auto it : v[nod]){
			son = it.first;
			sondist = it.second;
			if(dist + sondist < d[son]){
				if(seen[son] == n)
					return out << "Ciclu negativ!", 0;
				d[son] = dist + sondist;
				seen[son]++;
				q.push({son, d[son]});
			}
		}
	}
	for(int i = 2; i <= n; i++)
		out << d[i] << ' ';
	return 0;
}