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

#define Nmax 50011
#define Mmax 250011

#define x second.first
#define y second.second
#define cost first

#define oo 1<<30

pair< int , pair<int,int> > A[Mmax];
int Cost[Nmax],N,M,Ciclu;

ifstream F("bellmanford.in");
ofstream G("bellmanford.out");

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
		F>>A[i].x>>A[i].y>>A[i].cost;
	for (int i=1;i<=N;++i)
		Cost[i]=oo;
	
	int Start=1;
	Cost[Start]=0;
	
	for (int i=1;i<=N;++i)
		for (int j=1;j<=M;++j)
			if ( Cost[ A[j].x ] + A[j].cost < Cost[ A[j].y ] )
				Cost[ A[j].y ] = Cost[ A[j].x ] + A[j].cost;
	
	Ciclu=0;
	for (int i=1;i<=M && !Ciclu;i++)
        if( Cost[ A[i].x ]+ A[i].cost < Cost[ A[i].y ] )
            Ciclu=1;
	
	if ( Ciclu )
	{
		G<<"Ciclu negativ!\n";
		return 0;
	}
	for (int i=2;i<=N;++i)
		G<<Cost[i]<<' ';
	G<<'\n';
}