#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 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;
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);

do
{ok=0;
	i++;
while(!p.empty())
{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;
ok=1;
if(!t[v[xx][j].d])
{p.push(v[xx][j].d);
t[v[xx][j].d]==1;}


}
	
}
	
	
	
	
}while(ok||i==n);

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