# include <fstream>
# include <vector> 

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 ], queue [ 5000001 ], qs;
bool viz[50001];
vector <neighbour> G [ 50001 ];
const int inf = 2000000001;

int main(){

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

	int n, m, i, x, h;
	bool ok;
	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;
	
	h=0;	qs = 0;	ok = 1;
	queue [ qs ++ ] = 1;
	while ( h < qs && ok ){
		end = G [ queue [ h ] ] . end ();
		for ( it = G [ queue [ h ] ] . begin (); it != end; ++ it )
			if ( dist [ it -> y ] > dist [ queue [ h ] ] + ( it -> c ) ){
				dist [ it -> y ] = dist [ queue [ h ] ] + ( it -> c );
				queue [ qs ++ ] = it -> y;
				++ cnt [ it -> y ];
				if ( cnt [ it -> y ] >= n ) ok = 0;
			}
		++ h;
	}
	
	if ( !ok )
		g << "Ciclu negativ!\n";
	else{
		for ( i = 2; i <= n; ++ i )
			g << dist [ i ] << ' ';
		g << '\n';
	}
	g . close ();
	
	return 0;

}