#include<stdio.h>
#define dim 5000
#define inf 5000000
using namespace std;

int i,n,m,x,y,man,x0,c[dim][dim],d[dim],j,k,pre[dim];
short int ok;

int main()
{
 FILE *f=fopen("bellmanford.in","r"), *g=fopen("bellmanford.out","w");
 
fscanf(f,"%d%d",&n,&m);

for(i=1;i<=n;i++)
  for(j=i+1;j<=n;j++)
	c[i][j]=c[j][i]=inf;
  

 for(i=1;i<=m;i++)
 {fscanf(f,"%d%d%d",&x,&y,&man);
  c[x][y]=man;
 }
 
 
 for(i=1;i<=n;i++)
{d[i]=c[1][i]; pre[i]=1;}
pre[1]=0;


for(i=1;i<=n;i++)
 {ok=0;
  for(j=1;j<=n;j++)
  for(k=1;k<=n;k++)
	if(c[j][k]!=inf && d[k]>d[j]+c[j][k])
	{d[k]=d[j]+c[j][k];
	 pre[k]=j;
	 ok=1;}
 }


if(ok) fprintf(g,"Ciclu negativ!");

else
for(i=2;i<=n;i++)
{if(d[i]!=inf) fprintf(g,"%d ",d[i]);
else fprintf(g,"0 ");
}
fprintf(g,"\n");
	
fclose(f);
fclose(g);
return 0;
}