#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

#define pb push_back
#define mp make_pair
#define OO 99999999

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

vector <int> G[50050],C[50050],Q;
int n,m;
int d[50050];
int cnt[50050];
bool InQ[50050];
bool NG;

void Read();
void Bellman();
void Write();

int main()
{
	Read();
	Bellman();
	Write();
}

void Read ()
{
	f >> n >> m;
	int x ,y,d;
	for ( int i = 1; i <= m ; i++ )
	{
		f >> x >> y >> d;
		G[x].pb(y);
		C[x].pb(d);
	}

}

void Bellman()
{
	for ( int i = 1; i <= n ; i++ )
		d[i] = OO;
	
	d[1] = 0;
	InQ[1] = true;
	Q.pb(1);
	NG = false;
	int x,c,nod;
	
	while ( Q.size() > 0 && NG == false )
	{
		x = Q.front();
		Q.erase(Q.begin());
		InQ[x] = false;
		
		for ( unsigned int i = 0 ; i < G[x].size() ; i++ )
		{
			nod = G[x][i];
			c = C[x][i];
			if ( d[nod] > d[x] + c )
			{
				d[nod] = d[x] + c;
				if ( InQ[nod] == false )
				{
					if ( cnt[nod] > n )
						NG = true;
					else
					{
						Q.pb(nod);
						InQ[nod] = true;
						cnt[nod]++;
					}
				}
			}
		}
	}
}

void Write ()
{
	if ( NG )
		g << "Ciclu negativ!\n";
	else
		for ( int i = 2; i <= n ; i++ )
			g << d[i] << ' ';
}