#include <fstream>
#include <vector>
#include <queue>

#define nmax 50001
#define mmax 250001

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int oo = (1 << 30);
int n, m;
int r[nmax], d[nmax];
vector<pair<int, int>> l[nmax];

bool bellmanford(int nod)
{
	for (int i = 1; i <= n; i++)
		d[i] = oo;

	queue<int> q;

	d[nod] = 0;
	q.push(nod);

	while (!q.empty())
	{
		int k = q.front();
		q.pop();

		for (pair<int, int> vec : l[k])
		{
			int y = vec.first;
			int c = vec.second;

			if (d[y] > d[k] + c)
			{
				d[y] = d[k] + c;
				r[y]++;
				if (r[y] == n)
					return true;
				q.push(y);
			}
		}
	}

	return false;
}

int main()
{
	in >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		in >> x >> y >> c;
		l[x].push_back(make_pair(y, c));
	}
	in.close();

	bool cicluNegativ = bellmanford(1);
	if (cicluNegativ)
		out << "Ciclu negativ!";

	else
		for (int i = 2; i <= n; i++)
			if (d[i] != oo)
				out << d[i] << ' ';
	out.close();

	return 0;
}