#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<climits>
using namespace std;

int n, m;
vector< pair<int, int> > adj[50000];
int dist[50000], in_queue[50000], times[50000];

int main() {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	int u, v, c, i, current;
	bool cycle = false;
	queue<int> modified;
	scanf("%d %d", &n, &m);
	for(i = 0; i < m; i++) {
		scanf("%d %d %d", &u, &v, &c);
		u--, v--;
		adj[u].push_back(make_pair(v, c));
	}
	for(i = 0; i < n; i++) {
		dist[i] = INT_MAX;
	}
	modified.push(0);
	dist[0] = 0;
	in_queue[0] = 1;
	times[0] = 1;
	while(!modified.empty() && !cycle) {
		current = modified.front();
		modified.pop();
		in_queue[current] = 0;

		for(vector< pair<int, int> >::iterator it = adj[current].begin(); it != adj[current].end(); ++it) {
			// try to relax
			if(dist[current] + it->second < dist[it->first]) {
				dist[it->first] = dist[current] + it->second;
				if(in_queue[it->first] == 0) {
					modified.push(it->first);
					in_queue[it->first] = 1;
					times[it->first]++;
					if(times[it->first] == n + 1) {
						cycle = true;
					}
				}	
			}
		}
	}
	if(cycle) {
		printf("Ciclu negativ!\n");
	} else {
		for(i = 1; i < n; i++) {
			printf("%d ", dist[i]);
		}
	}
	return 0;
}