#include <fstream>
#define sizen 31010
#define sizem 250010
#define infinity 1<<30

using namespace std;
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

int n, m, d[sizen];
short a[sizen][sizen];

struct edges
{
	int i, j, p;
}edge[sizem];

void bellmanford(int s)
{
	for(int i = 1; i <= n; i ++)
		d[i] = infinity;
	
	d[s] = 0;
	
	for(int i = 1; i <= n; i ++)
		for(int j = 0; j < m; j ++)
			if(d[edge[j].j] > d[edge[j].i] + edge[j].p)
				d[edge[j].j] = d[edge[j].i] + edge[j].p;
}

int main()
{
	f >> n >> m;
	int x, y, p;
	for(int i = 0; i < m; i ++)
	{
		f >> x >> y >> p;
		a[x][y] = p;
		edge[i].i = x;
		edge[i].j = y;
		edge[i].p = p;
	}
	bellmanford(1);
	bool ok = true;
	for(int i = 2; i <= n; i ++)
		if(d[i] >= 0)
		{
			ok = false;
			break;
		}
	if(!ok)
		for(int i = 2; i <= n; i ++)
			g << d[i] << ' ';
	else
		g << "Ciclu negativ!";
}