#include <fstream>

#include <vector>

#include <queue>

#define INF 33333



using namespace std;

ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");



struct edge

{

	int nod, c;

};



vector <edge> a[50005];

int dmin[50005], nr[50005];



queue <int> q;



int n, m, k;



void read();

bool Bellman_Ford();

void write();



int main()

{

	read();

	write();



	return 0;

}



void read()

{

	int i, x;

	edge muchie;

	muchie.nod = muchie.c = 0;



	fin >> n >> m;



	for (i = 1; i <= n + 1; i++)

	{

		a[i].push_back(muchie);

		dmin[i] = INF;

	}



	dmin[1] = 0;



	for (i = 1; i <= m; i++)

	{

		fin >> x >> muchie.nod >> muchie.c;

		a[x].push_back(muchie); a[x][0].c++;

	}



	q.push(1);

}



bool Bellman_Ford()

{

	int i, x;

	bool negative_circuit = false;



	while (!q.empty() && !negative_circuit)

	{

		x = q.front(); q.pop();



		for (i = 1; i <= a[x][0].c; i++)

			if (dmin[a[x][i].nod] > dmin[x] + a[x][i].c)

			{

				dmin[a[x][i].nod] = dmin[x] + a[x][i].c;

				nr[a[x][i].nod]++;



				if (nr[a[x][i].nod] == n)

				{

					negative_circuit = true; break;

				}

				q.push(a[x][i].nod);

			}

	}



	return negative_circuit;

}



void write()

{

	if (Bellman_Ford())

		fout << "Ciclu negativ!\n";

	else

	{

		for (int i = 2; i <= n; i++)

			fout << dmin[i] << ' ';

		fout << '\n';

	}

}