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

using namespace std;

//Bellman Ford algorithm with a queue ( using BFS )
//supposed to obtain 100p.

struct neighbour{
	int y, c;
};

int dist [ 50001 ], cnt [ 50001 ];
bool viz[50001];
vector <neighbour> G [ 50001 ];
queue <int> q;
const int inf = 2000000001;

int main(){

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

	int n, m, i, x;
	bool negativeCycle;
	neighbour a;
	vector <neighbour> :: iterator it, end;

	f >> n >> m;
	for ( i = 0; i < m; ++ i ){
		f >> x >> a . y >> a . c ;
		G [ x ] . push_back ( a );
	}
	f . close ();
	
	for ( i = 2; i <= n; ++ i )
		dist [ i ] = inf;
	
	negativeCycle = false;
	q . push ( 1 );
	while ( ! q . empty() && ! negativeCycle ){
		end = G [ q . front () ] . end ();
		for ( it = G [ q . front () ] . begin (); it != end; ++ it )
			if ( dist [ it -> y ] > dist [ q . front() ] + ( it -> c ) ){
				dist [ it -> y ] = dist [ q . front () ] + ( it -> c );
				q . push ( it -> y );
				++ cnt [ it -> y ];
				if ( cnt [ it -> y ] == n )
					negativeCycle = true;
			}
		q . pop();
	}
	
	if ( negativeCycle )
		g << "Ciclu negativ!\n";
	else{
		for ( i = 2; i <= n; ++ i )
			g << dist [ i ] << ' ';
		g << '\n';
	}
	g . close ();
	
	return 0;

}