#include<fstream>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

struct muchie{
	int a, b, cost;
};

const int nmax = 50006, mmax = 250006, inf = 1006 * mmax;
int n, m, dist[nmax];
muchie vm[mmax];
bool ok;

int main(){
	int player_unu=0;

	in>>n>>m;
	for(int i = 1; i<=m; i++)
		in>>vm[i].a>>vm[i].b>>vm[i].cost;

	for(int i = 2; i<=n; i++)
		dist[i] = inf;

	for(int i = 1; i<n; i++)
		for(int j = 1; j<=m; j++)
			if(dist[vm[j].b]>dist[vm[j].a] + vm[j].cost)
				dist[vm[j].b] = dist[vm[j].a] + vm[j].cost;

	for(int j = 1; j<=m; j++)
	{
		if(dist[vm[j].b]>dist[vm[j].a] + vm[j].cost)
		{
			ok = 1;
			break;
		}
	}

	if(ok==1)
		out<<"Ciclu negativ!\n";
	else
	{
		for(int i = 2; i<=n; i++)
			out<<dist[i]<<' ';
	}

	return player_unu;
}