#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int inf = 1 << 30;
const int NMAX = 50005;
int N, M;
int dist[NMAX];
vector< pair<int, int> > edges[NMAX];

void read() {
	freopen( "bellmanford.in", "r", stdin );
//	freopen( "bellmanford.out", "w", stdout );
	scanf("%i %i", &N, &M);
	int from, to, cost;
	for( int i = 0; i < M; i++ ) {
		scanf("%i %i %i", &from, &to, &cost);
		edges[from].push_back(make_pair(to, cost));
	}
}

void solve() {
	dist[1] = 0;
	for( int i = 2; i <= N; i++ )
		dist[i] = inf;
	for( int q = 1; q < N; q++ ) {
		for( int i = 1; i <= N; i++ )
			if ( dist[i] < inf )
				for( int j = 0; j < (int) edges[i].size(); j++ ) {
					pair<int, int> p = edges[i][j];
					if( dist[i] + p.second < dist[p.first] )
						dist[p.first] = dist[i] + p.second;
				}
	}

	for( int q = 1; q < N; q++ ) {
		for( int i = 1; i <= N; i++ )
			if ( dist[i] < inf )
				for( int j = 0; j < (int) edges[i].size(); j++ ) {
					pair<int, int> p = edges[i][j];
					if( dist[i] + p.second < dist[p.first] ) {
						printf("Ciclu negativ!");
						return;
					}

				}
	}

	for( int i = 2; i <= N; i++)
		printf("%i ", dist[i]);
}

int main() {
	read();
	solve();
	return 0;
}