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

	return 0;

}