#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define let(X, A) typeof(A) X(A)
#define ech(It, A) for (let( It, A.begin() ); It != A.end(); ++It)
const int inf = 1<<29;
const int MAXN = 5e4;

struct edge {
	int w;
	int v;
	edge ( int w, int v ) : w(w), v(v) {}
};

int main() {
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	srand( time(NULL) );
	int n, m;
	fin >> n >> m;
	vector<edge> adjl1[n+1], adjl2[n+1];
	vector<int> rpermutation( n+1 );
	for (int i=1; i<=n; ++i) {
		rpermutation[i] = i;
	}
	random_shuffle( rpermutation.begin()+2, rpermutation.end() );

	for (int u, v, w, i=0; i<m; ++i) {
		fin >> u >> v >> w;
		u = rpermutation[u];
		v = rpermutation[v];
		if (u < v)
			adjl1[u].push_back( edge(w, v) );
		else
			adjl2[u].push_back( edge(w, v) );
	}

	vector<int> dist( n+1, inf );
	dist[1] = 0;
	bitset<MAXN+1> change1, change2;
	change1.set(1);

	for (int i=1; ; ++i) {
		for (int j=1; j<=n; ++j) {
			if ( change1[j] || change2[j] ) {
				ech ( it, adjl1[j] ) {
					if ( dist[it->v] > dist[j] + it->w ) {
						dist[it->v] = dist[j] + it->w;
						change2.set( it->v );
					}
				}
			}
		}

		for (int j=n; j>=1; --j) {
			if ( change1[j] || change2[j] ) {
				ech ( it, adjl2[j] ) {
					if ( dist[it->v] > dist[j] + it->w ) {
						dist[it->v] = dist[j] + it->w;
						change2.set( it->v );
					}
				}
			}
		}
		if (change2.none() || i == n )  {
			cout << i;
			break;
		}
		swap( change1, change2 );
		change2.reset();
	}

	if ( change2.any() ) {
		fout << "Ciclu negativ!";
		return 0;
	}

	for (int i=2; i<=n; ++i) {
		fout << dist[ rpermutation[i] ] << ' ';
	}
	return 0;
}