# 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, tp, nd;
	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;
	
	ok = 1;
	q . push ( 1 );
	while ( ! q . empty() && ok ){
		tp = q . front ();
		end = G [ tp ] . end ();
		for ( it = G [ tp ] . begin (); it != end; ++ it ){
			nd = dist [ tp ] + ( it -> c );
			if ( dist [ it -> y ] > nd ){
				dist [ it -> y ] = nd;
				q . push ( it -> y );
				++ cnt [ it -> y ];
				if ( cnt [ it -> y ] >= n ) ok = 0;
			}
		}
		q . pop();
	}
	
	if ( !ok )
		g << "Ciclu negativ!\n";
	else{
		for ( i = 2; i <= n; ++ i )
			g << dist [ i ] << ' ';
		g << '\n';
	}
	g . close ();
	
	return 0;

}