#include <fstream>
#include <vector>
#include <queue>
#define INF 33333

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.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';
	}
}