#include <fstream>
#include <vector>
#define siz 50010
#define inf 2000000000

using namespace std;

struct adat {
	long kezd,veg,ut;
} t;

long n,m,i,j,a,b,x,dist[siz];
char ok;
vector< adat > v;

int neg() {
	if (ok==0) return 0;
	for (int q=0;q<m;++q)
		if (dist[v[q].veg]>dist[v[q].kezd]+v[q].ut) return 1;
	return 0;
}

int main() {
	ifstream in("bellmanford.in");
	ofstream out("bellmanford.out");

	in >> n >> m;
	for (i=2;i<=n;++i) dist[i]=inf;
	for (i=1;i<=m;++i) {
		in >> a >> b >> x;
		t.kezd=a;
		t.veg=b;
		t.ut=x;
		v.push_back(t);
	}

	ok=1;
	for (i=1;i<n&&ok==1;++i) {
		ok=0;
		for (j=0;j<m;++j)
			if (dist[v[j].veg]>dist[v[j].kezd]+v[j].ut) {
				dist[v[j].veg]=dist[v[j].kezd]+v[j].ut;
				ok=1;
			}
	}


	if (neg()) out << "Ciclu negativ!"; else
		for (i=2;i<=n;++i) out << dist[i] << " ";

	in.close();
	out.close();

	return 0;
}