#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
struct muchie{int d,c;};
muchie mm;
int inf=0x3f3f3f3f;
bool t[50005];
int nr[50005];
int main()
{ifstream f("bellmanford.in");
ofstream h("bellmanford.out");
vector< vector <muchie> > v(50005);
queue <int> p;
int a,n,m,i,j,xx,ok=0;
int dd[50005];






f>>n>>m;

for(i=2;i<=n;i++)
	dd[i]=inf;
dd[1]=0;

for(i=1;i<=m;i++)
	{f>>a>>mm.d>>mm.c;
v[a].push_back(mm);}

p.push(1);


	
while(!p.empty()&&!ok)
{xx=p.front();
p.pop();
t[xx]=0;
for(j=0;j<v[xx].size();j++)
if(dd[xx]+v[xx][j].c<dd[v[xx][j].d])
{dd[v[xx][j].d]=dd[xx]+v[xx][j].c;
if(!t[v[xx][j].d])
{p.push(v[xx][j].d);
t[v[xx][j].d]==1;
nr[v[xx][j].d]++;
if(nr[v[xx][j].d]>n)
	ok=1;
}


}
	
}
	
	
	
	


	if(ok==1)
		h<<"Ciclu negativ!";
	else
	
	for(i=2;i<=n;i++)
		h<<dd[i]<<" ";
	
	
	
	
	
	
	
	return 0;}