program bellman_ford;
const inf=maxlongint;
var t:array[0..2,1..500000] of longint;
    start,d,count:array[1..50000] of longint;
    i,j,m,n:longint;
    f,g:text;

procedure citeste_static;
var i,j,cost,k:longint;
begin
 assign(f,'bellmanford.in'); reset(f);
 readln(f,n,m);
 k:=0;
 while m>0 do
  begin
   readln(f,i,j,cost);
   k:=k+1;
   t[0,k]:=j;
   t[1,k]:=start[i];
   t[2,k]:=cost;
   start[i]:=k;
   m:=m-1;
  end;
 close(f);
end;

function bellman_ford(x:longint):boolean;
var i,j,k,p:longint;
    ok:boolean;
begin
 for i:=1 to n do
  d[i]:=inf;
 d[x]:=0; count[x]:=1;
 for i:=1 to n do
  begin
   p:=start[i];
   while p<>0 do
    begin
     if d[t[0,p]]>d[i]+t[2,p] then
      begin
       d[t[0,p]]:=d[i]+t[2,p];
       count[t[0,p]]:=count[t[0,p]]+1;
      end;
     if count[t[0,p]]>=n then
      ok:=false;
     p:=t[1,p];
    end;
  end;
 bellman_ford:=ok;
end;

procedure solve;
var i:longint;
begin
 assign(g,'bellmanford.out'); rewrite(g);
 if bellman_ford(1) then
  for i:=2 to n do
   write(g,d[i],' ')
 else
  write(g,'Ciclu negativ');
 close(g);
end;

begin
 citeste_static;
 solve;
end.