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

using namespace std;

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

struct muchie
{
	int x, c;
};

int n, m, ok=1, d[50005], nr[50005];
vector<muchie> L[50005];
queue<int> C;

int main()
{
	int i, x, y;
	muchie aux;

	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> aux.x >> aux.c;
		L[x].push_back(aux);
	}
	for (i = 2; i <= n; i++)
		d[i] = INF;
	C.push(1);
	while (!C.empty() && ok)
	{
		x = C.front();
		C.pop();
		for (i = 0; i < L[x].size(); i++)
		{
			y = L[x][i].x;
			if (d[y] > d[x] + L[x][i].c)
			{
				d[y] = d[x] + L[x][i].c;
				nr[y]++;
				C.push(y);
				if (nr[y] == n)
				{
					ok = 0;
					break;
				}
			}
		}
	}
	if (!ok)
		fout << "Ciclu negativ!\n";
	else
	{
		for (i = 2; i <= n; i++)
			fout << d[i] << ' ';
		fout << '\n';
	}
	return 0;
}