#include<iostream>
#include<stdio.h>

using namespace std;

long noduri,muchii;
const long long infinit = 2000000000;

struct
{
	long from;
	long to;
	long cost;
} muchie[251000];

int d[251000];

int BellmanFord(long start)
{
	for (long i=1; i<= noduri; i++) d[i] = infinit;
	d[start] = 0;
	for (long i=1; i < noduri; i++)
	{
		for (long j=1; j <= muchii; j++)
		{
			// relaxeaza
			if (d[muchie[j].from] + muchie[j].cost < d[muchie[j].to]) 
			{
				d[muchie[j].to] = d[muchie[j].from] + muchie[j].cost;
			}
		}
	}
	// verifica daca nu este un ciclu negativ
	for (long i=1; i <= muchii; i++)
	{
		if (d[muchie[i].to] > d[muchie[i].from] + muchie[i].cost)  return 0;
	}
	return 1;
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	cin >> noduri >> muchii;
	for (long i=1; i<= muchii; i++)
	{
		cin >> muchie[i].from >> muchie[i].to >> muchie[i].cost;
	}
	if (BellmanFord(1))
	{
		for (long i=2; i <= noduri; i++)
		{
			cout << d[i] << " ";
		}
	}
	else
	{
		cout << "Ciclu negativ!";
	}
	return 0;
}