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

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanfor.out");
const int nmax = 50001;
const int inf = 1000001;
int n, m;

struct duo
{
	int adj, w;
};
vector <duo> ad[nmax];
int d[nmax];
void init(int s)
{
	for (int i = 1; i <= n; i++)
	{
		d[i] = inf;
	}
	d[s] = 0;
}
void relax(int u, int v, int w)
{
	if (d[v] > d[u] + w)
		d[v] = d[u] + w;
}


bool bellman(int s)
{
	init(s);
	for (int k = 1; k <= n - 1; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < ad[i].size(); j++)
			{
				relax(i, ad[i][j].adj, ad[i][j].w);
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < ad[i].size(); j++)
		{
			if (d[i]>d[ad[i][j].adj] + ad[i][j].w)
				return 0;
		}
	}
	return 1;
}


int main()
{
	fin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		int x;
		duo h;
		fin >> x >> h.adj >> h.w;
		ad[x].push_back(h);
	}
	if (!bellman(1))
	{
		fout << "Ciclu negativ!";
	}
	else
	{
		for (int i = 2; i <= n; i++)
		{
			fout << d[i] << ' ';
		}
	}
}