#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int inf = 1 << 30;
const int NMAX = 50005;
int N, M;
int dist[NMAX], count[NMAX];
vector< pair<int, int> > edges[NMAX];
queue<int> nodes;

void read() {
	freopen( "bellmanford.in", "r", stdin );
	freopen( "bellmanford.out", "w", stdout );
	scanf("%i %i", &N, &M);
	int from, to, cost;
	for( int i = 0; i < M; i++ ) {
		scanf("%i %i %i", &from, &to, &cost);
		edges[from].push_back(make_pair(to, cost));
	}
}

int solve() {
	for( int i = 2; i <= N; i++ )
		dist[i] = inf;
	nodes.push(1);
	pair<int, int> p;
	while( !nodes.empty() ) {
		int node = nodes.front();
		nodes.pop();
		count[node]++;
		if( count[node] == N )
			return 0;
		for( int i = 0; i < (int) edges[node].size(); i++) {
			p = edges[node][i];
			if( dist[i] + p.second < dist[p.first] ) {
				dist[p.first] = dist[i] + p.second;
				nodes.push(p.first);
			}
		}
	}
	return 1;
}

int main() {
	read();
	int ok = solve();
	if (ok)
		printf("Ciclu negativ!");
	else {
		for( int i = 2; i <= N; i++)
			printf("%i ", dist[i]);
	}

	return 0;
}