#include <stdio.h>
#include <limits.h>
#include <vector>

#include <queue>

#define INF INT_MAX

using namespace std;

FILE * fin;
FILE * fout;

int n,m;

struct TNOD
{
	int Dest,Weight;
};

queue <int> x;
vector <TNOD> v[50001];

int d[50001],nr[50001];



//------------------------------------------
void citire()
{
	fin = fopen("bellmanford.in","r");
	fout = fopen("bellmanford.out","w");
	
	fscanf(fin,"%d %d",&n,&m);
	int i,a;
	TNOD nod;


	for (i=1; i<=m; i++)
	{
		fscanf(fin,"%d %d %d",&a,&nod.Dest,&nod.Weight);
		
		d[i]=INF;
		
		v[a].push_back(nod);
	}
	
	fclose(fin);
}
//------------------------------------------
int solve()
{
	x.push(1);
	
	int Node,i;
	
	d[1]=0;
	
	int Dest,Cost;

	
	while (x.size()>0)
	{
		Node=x.front();
		
		for (i=0; i<v[Node].size(); i++)
		if (v[Node][i].Weight!=0)
		{
			Dest=v[Node][i].Dest;
			Cost=v[Node][i].Weight+d[Node];
			
			if ((d[Dest]>Cost))
			{
				d[Dest]=Cost;
				//pre[
				
				x.push(Dest);
				
				nr[Dest]++;
				if (nr[Dest]>n)
				{
					return 1;
				}
			}
		}
		
		x.pop();
	}
	
	return 0;
}
//------------------------------------------
void afisare()
{
	int i;
	for (i=2; i<=n; i++)
	{
		if (d[i]==INF)  d[i]=0;
		
		fprintf(fout,"%d ",d[i]);
	}
}
//------------------------------------------

int main()
{
	citire();
	
	if (solve()==0)
	{
		afisare();
	} else
	{
		fprintf(fout,"Ciclu negativ!");
	}
	
	fclose(fout);
	return 0;
}