#include <cstdio>
#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;
	freopen ("dijkstra.in", "rt", stdin);
	freopen ("dijkstra.out", "wt", stdout);
	scanf ("%d%d", &n, &m);
	G.resize (n + 1);
	for (i = 0; i < m; ++ i) {
		scanf ("%d%d%d", &x, &y, &c);
		G [x].push_back (make_pair (y, c));
	}
	d = bellman_ford (1, n, G, ok);
	if (! ok) {
		printf ("Ciclu negativ!");
	}
	else {
		printf ("%d", d [2]);
		for (i = 3; i <= n; ++ i) {
			printf (" %d", d [i]);
		}
		printf ("\n");
	}
	return 0;
}