#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

#define nmax 50001
#define inf LONG_MAX 

unsigned short int n, viz[nmax];
unsigned long int m;
long int d[nmax];

vector < pair<unsigned short int, short int> > v[nmax];
queue <unsigned short int> Q;

void citire()
{
	unsigned short int x, y, c;
	
	freopen("bellmanford.in", "r", stdin);
	scanf("%hu %lu", &n, &m);
	for(unsigned long int i=1; i<=m; i++)
	{
		scanf("%hu %hu %hd", &x, &y, &c);
		v[x].push_back( make_pair(y, c) );
	}
}

void afisare()
{
	for(unsigned short int i=2; i<=n; i++)
		printf("%ld ", d[i]);
}

void init()
{
	for(unsigned short int i=1; i<=n; i++)
		d[i] = inf;
	d[1] = 0;
}

bool bell()
{
	unsigned short int nod, i, dest;
	long int cost;
	Q.push(1);
	while( !Q.empty() )
	{
		nod = Q.front(); Q.pop();
		for(i=0; i<v[nod].size(); i++)
		{
			cost = d[nod] + v[nod][i].second; 
			dest = v[nod][i].first;
			if( cost < d[ dest ] )
			{
				d[ dest ] = cost;
				Q.push( dest );
				viz[ dest] ++;
				if( viz[dest] > n )
					return true;
			}
		}
	}
	return false;
}

int main()
{
	freopen("bellmanford.out", "w", stdout);
	citire();
	init();
	
	if( bell() )
		printf("Ciclu negativ!\n");
	else
		afisare();

	return 0;
}