#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;


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

struct Edge
{
	int a, b, c;
}E[20001];

int N, M,length = 0;
int D[50001],i,j,a,b,c;

int main()
{
	in >> N >> M;
	for (i = 1;i <= M;++i)
	{
		in >> a >> b >> c;
		E[++length].a = a;
		E[length].b = b;
		E[length].c = c;
	}
	for (i = 1;i <= N;++i)
		D[i] = (1 << 30);
	D[1] = 0;
	for (i = 1;i <= N;++i)
	{
		for (j = 1;j <= length;++j)
			if (D[E[j].a] + E[j].c < D[E[j].b])
				D[E[j].b] = D[E[j].a] + E[j].c;
	}

	for (i = 1;i <= M;++i)
		if (D[E[j].a] + E[j].c < D[E[j].b])
		{
			out << "Ciclu negativ!";
			return 1;
		}

	for (i = 2;i <= N;++i)
		out << D[i] << " ";

	return 0;
}