#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
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) {}
	bool operator > (  const edge & a ) const {
		return w > a.w;
	}
};

int main() {
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	int n, m;
	fin >> n >> m;
	vector<edge> adjl[n+1];
	for (int u, v, w, i=0; i<m; ++i) {
		fin >> u >> v >> w;
		adjl[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<n; ++i) {
		for (int j=1; j<=n; ++j) {
			if (change1[j]) {
				ech ( it, adjl[j] )
					if ( dist[it->v] > dist[j] + it->w ) {
						dist[it->v] = dist[j] + it->w;
						change2[it->v] = true;
					}
			}
		}
		if (change2.none()) break;
		swap( change1, change2 );
		change2.reset();
	}

	for (int j=1; j<=n; ++j)
		ech( it, adjl[j] )
			if ( dist[it->v] > dist[j] + it->w ) {
				fout << "Ciclu negativ!";
				return 0;
			}

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