#include<fstream>
#define inf 2000000000
#define nmax 50002
#define mmax 250002
#define tmax 200
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct muchie
{
	int a,b,c;
}v[mmax];
int n,m,d[nmax];
void sol()
{
	int i,ok=1,nr=0;
	while(ok&&nr<=tmax)
	{
	    ok=0;
	    for(i=1;i<=m;i++)
	     if(d[v[i].a]+v[i].c<d[v[i].b])
	     {
	         d[v[i].b]=d[v[i].a]+v[i].c;
	         ok=1;
         }
         nr++;
	}
}

bool ciclu()
{
	int i;
	for(i=1;i<=m;i++)
		if(d[v[i].a]+v[i].c<d[v[i].b])
		 return 0;
    return 1;
}

int main()
{
	f>>n>>m;
	int i;
	for(i=1;i<=m;i++)
		f>>v[i].a>>v[i].b>>v[i].c;
    for(i=2;i<=n;i++)
     d[i]=inf;
	sol();
	if(!ciclu())
	g<<"Ciclu negativ!";
	else
		for(i=2;i<=n;i++)
			g<<d[i]<<" ";
	return 0;
}