#include <iostream>
#include <fstream>
#include <string>
#include <limits>
using namespace std;
#define NMAX 50025
#define OO 1 << 29
//=============================================================
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");
//=============================================================
struct nod
{
	nod *adr;
	int inf;
	int cost;
} *A[NMAX];
//=============================================================
int n,m;
int d[NMAX];
int c[NMAX];
int v[NMAX];
bool Q[NMAX];
bool negativ;
//=============================================================
void Read ();
void Bellman ();
void End();
//=============================================================
//=============================================================
int main ()
{
	Read ();
	Bellman();
	End();
}
//=============================================================
//=============================================================
void Read ()
{
	f >> n >> m;
	int x, y , d;
	nod *p;
	for ( int i = 1; i <= m; i++ )
	{
		f >> x >> y >> d;
		p = new nod;
		p->inf = y;
		p->cost = d;
		p->adr = A[x];
		A[x] = p;
	}
}
//=============================================================
void Bellman()
{
	for ( int i = 2 ; i <= n ; i++ )
	{
		d[i] = OO;
		Q[i] = 0;
	}
	
	int p , u;
	d[1] = 0;
	
	c[1] = p = u = 1;
	Q[1] = true;
	nod *x;
	
	while ( p <= u && !negativ)
	{
		x = A[ c[p] ];
		Q[p] = false;
		for ( ; x ; x = x->adr )
		{
			int t = x->inf;
			if ( d[p] + x->cost < d[t] )
			{
				d[t] = d[p] + x->cost;
				
				if ( !Q[t] )
				{
					if ( v[t] > n )
					{
						negativ = true;
						return;
					}
					Q[t] = true;
					v[t]++;
					c[++u] = t;
				}
			}
		}
		p++;
	}
	
}
//=============================================================
void End ()
{
	if ( negativ )
		g << "Ciclu negativ!";
	else
		for ( int i = 2; i <= n ; i++ )
			g << d[i] << ' ';
}