#include <cstdio>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>

using namespace std;

vector <int> bellman_ford (int sursa, int n, vector <vector < pair <int, int> > > &G, bool &ok) {
	vector < pair <int, int> > :: iterator it;
	vector <int> len, d;
	queue <int> q;
	len.resize (n + 1);
	d.resize (n + 1, 1 << 30);
	ok = true;
	d [sursa] = 0;
	len [sursa] = 0;
	q.push (sursa);
	while (ok && !q.empty ()) {
		sursa = q.front ();
		q.pop ();
		for (it = G [sursa].begin (); it != G [sursa].end (); ++ it) {
			if (d [it->first] > d [sursa] + it->second) {
				d [it->first] = d [sursa] + it->second;
				len [it->first] = 1 + len [sursa];
				q.push (it->first);
				if (len [it->first] >= n) {
					ok = false;
					break;
				}
			}
		}
	}
	return d;
}

int main () {
	vector <vector < pair <int, int> > > G;
	vector <int> d;
	bool ok;
	int i, n, m, x, y, c;
	ifstream f ("bellmanford.in");
	ofstream g ("bellmanford.out");
	f >> n >> m;
	G.resize (n + 1);
	for (i = 0; i < m; ++ i) {
		f >> x >> y >> c;
		G [x].push_back (make_pair (y, c));
	}
	d = bellman_ford (1, n, G, ok);
	if (! ok) {
		g << "Ciclu negativ!\n";
	}
	else {
		if (d [2] == (1 << 30)) {
			d [2] = 0;
		}
		g << d [2];
		for (i = 3; i <= n; ++ i) {
			if (d [i] == (1 << 30)) {
				d [i] = 0;
			}
			g << " " << d [i];
		}
		g << "\n";
	}
	return 0;
}