#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 50005;
const int INF = 0x3f3f3f3f;
const char infile[] = "bellmanford.in";
const char outfile[] = "bellmanford.out";

vector < pair < int, int > > G[ MAX_N ];
queue <int> Q;

int N, M, negative;
int dist[ MAX_N ], count_nodes[ MAX_N ], use[ MAX_N ];

void read(){
	int i, x, y, c;
	freopen( infile, "r", stdin );
	scanf( "%d %d", &N, &M );
	for( i = 1; i <= M; ++i ){
		scanf( "%d %d %d", &x, &y, &c );
		G[ x ].push_back( make_pair( y, c ) );
	}
	fclose( stdin );
}

void initialize(){
	int i;
	for( i = 2; i <= N; ++i )
		dist[ i ] = INF;
}

void bellman_ford(){
	vector < pair < int, int > > :: iterator i;
	int new_node, new_dist, node;
	initialize();
	Q.push( 1 );
	use[ 1 ] = 1;
	count_nodes[ 1 ] = 1;
	
	while( !Q.empty() && !negative ){
		node = Q.front();
		Q.pop();
		use[ node ] = 0;

		for( i = G[ node ].begin(); i != G[ node ].end(); ++i ){
			new_node = i->first;
			new_dist = i->second;
			if( dist[ new_node ] > dist[ node ] + new_dist ){
				dist[ new_node ] = dist[ node ] + new_dist;
				if( !use[ new_node ] ){
					if( count_nodes[ new_node ] > N )
						negative = 1;
					else{
						Q.push( new_node );
						use[ new_node ] = 1;
						count_nodes[ new_node ] ++;
					}
				}
			}
		}
	}
}

void write(){
	int i;
	freopen( outfile, "w", stdout );
	if( negative )
		printf( "Ciclu negativ!\n" );
	else
		for( i = 2; i <= N; ++i )
			printf( "%d ", dist[ i ] );
	fclose( stdout );
}


int main(){
	read();
	bellman_ford();
	write();
	return 0;
}