#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 50005
#define mmax 250005
#define inf (1<<30)
using namespace std;

struct edge { int a, b, w; };
vector <edge> v;

edge attrib(int x, int y, int z) { edge T; T.a=x; T.b=y; T.w=z; return T; }
int n, m, a, b, c, best[nmax], pre[nmax];
bool cycle = false;

void bellmanford() {
	for(int i=2; i<=n; i++) best[i] = inf;

	for(int i=1; i<=n; i++)
		for(int j=0; j<v.size(); j++)
			if(best[v[j].a] + v[j].w < best[v[j].b]) {
				best[v[j].b] = best[v[j].a] + v[j].w;
				pre[v[j].b] = v[j].a;
			}

	for(int j=0; j<v.size(); j++)
		if(best[v[j].a] + v[j].w < best[v[j].b]) cycle = true;
}			

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

	f>>n>>m;
	for(int i=1; i<=m; i++) {
		f>>a>>b>>c;
		v.push_back(attrib(a, b, c));
	}

	bellmanford();

	if(cycle) g<<"Ciclu negativ!";
	else for(int i=2; i<=n; i++) g<<best[i]<<" ";

	g<<"\n";
	return 0;
}