#include<fstream.h>
#include<iostream.h>
const int inf=1<<30;
int a[3][100000],d[100000],i,j,n,m,ok=1;
int main()
{
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
fin>>n>>m;
for(i=1;i<=m;i++)fin>>a[0][i]>>a[1][i]>>a[2][i];
for(i=2;i<=n;i++)d[i]=inf;
for(i=1;i<n;i++)
	for(j=1;j<=m;j++)if(d[a[1][j]]>d[a[0][j]]+a[2][j])d[a[1][j]]=d[a[0][j]]+a[2][j];
for(i=1;i<=m && ok;i++)if(d[a[1][i]]>d[a[0][i]]+a[2][i])ok=0;
if(!ok)fout<<"Ciclu negativ!";
else for(i=2;i<=n;i++)fout<<d[i]<<' ';
return 0;
}