#include<fstream>
#include<bitset>
#include<utility>
#include<queue>
#include<vector>
using namespace std;

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

queue<int> que;
bitset<50000> in_queue;
int count_queue[50000], dist[50000];
vector< pair<int, int> > adj[50000];

int main() {
	int n, m, i, u, v, c, current;
	bool no_cycles = true;
	fin >> n >> m;
	for(i = 0; i < m; i++) {
		fin >> u >> v >> c;
		adj[u-1].push_back(make_pair(v-1, c));
	}
	for(i = 0; i < n; i++) dist[i] = 0x3f3f3f;
	que.push(0);
	count_queue[0]++;
	in_queue[0] = 1;
	dist[0] = 0;
	while(!que.empty() && no_cycles) {
		current = que.front();
		que.pop();
		in_queue[current] = 0;
		for(vector< pair<int, int> >::iterator it = adj[current].begin(); it != adj[current].end(); it++) {
			if(dist[it->first] > dist[current] + it->second) {
				if(count_queue[it->first] >= n) no_cycles = false;
				else {
					dist[it->first] = dist[current] + it->second;
					count_queue[it->first]++;
					if(!in_queue[it->first]) {
						in_queue[it->first] = 1;
						que.push(it->first);
					}
				}
			}
		}
	}
	if(no_cycles == false) {
		fout << "Ciclu negativ!";
	} else {
		for(i = 1; i < n; i++) {
			fout << dist[i] << " ";
		}
	}
	return 0;
}