#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define NMAX 50000
#define INF 1000*NMAX

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

struct Node {
	int node, cost;
	Node ( int x, int c ) {
		node = x;
		cost = c;
	}
};

std::vector < Node* > edges[1 + NMAX];
std::queue < int > q;
bool inq[1 + NMAX];
int nq[1 + NMAX];
int dist[1 + NMAX];

int main() {

	int N, M;

	fin >> N >> M;

	for ( int i = 1; i <= M; ++i ) {
		int x, y, c;
		fin >> x >> y >> c;	
		Node* node = new Node ( y, c );
		edges[x].push_back ( node );
	}

	for ( int i = 1; i <= N; ++i ) 
		dist[i] = INF;

	q.push ( 1 );
	dist[1] = 0;
	nq[1] = 1;
	inq[1] = true;
	bool cycle = false;
	while ( !q.empty() ) {
		int p = q.front();
		q.pop();
		inq[p] = false;
		for ( int i = 0; i < edges[p].size(); ++i ) {
			int newNode = edges[p][i] -> node;
			if ( dist[p] + edges[p][i] -> cost < dist[newNode] ) {
				dist[newNode] = dist[p] + edges[p][i] -> cost;
				if ( !inq[newNode] ) {
					q.push ( newNode );
					++nq[newNode];
					if ( nq[newNode] == N ) {
						cycle = true;
						goto end;
					}
				}
			}
		}
	}

	end:

	if ( cycle == true )
		fout << "Ciclu negativ!\n";
	else 
		for ( int i = 2; i <= N; ++i )
			fout << dist[i] << ' ';

	return 0;
}