type muchie=^nod;
     nod = record n, c:longint; a:muchie; end;

var v:array[1..50000] of muchie;
    d:array[1..50000] of longint;
    chk:array[1..50000] of boolean;
    cod:array[1..50000] of longint;
    buf1, buf2:array [1..1 shl 17] of char;
    m, n, i, j, k, x, y, c, ct:longint;       // unde ct e numarul de elemente din cod (coada varfurilor)
    f, g:text;
    p:muchie;
    ok:boolean;

begin
assign (f, 'bellmanford.in'); settextbuf (f, buf1); reset (f);
assign (g, 'bellmanford.out'); settextbuf (g, buf2); rewrite (g);

readln (f, n, m);
for i := 2 to n do d[i]:=maxlongint;
d[1]:=0;

for i := 1 to m do
  begin
  readln (f, x, y, c);
  if v[x]= nil then begin new(v[x]); v[x]^.a:=nil; v[x]^.n:=y; v[x]^.c:=c; end
               else begin new (p); p^.c:=c; p^.n:=y; p^.a:=v[x]; v[x]:=p; end;
  end;

cod[1]:=1;
for i := 1 to n do
  begin
  ok:=false;
  ct:=1;
  fillchar (chk, n+1, false);
  j:=1;
  while j <= ct do
    begin
    k:=cod[j];
    p:=v[k];
    while p<> nil do
      begin
      if int64 (d[k]+p^.c) < d[p^.n] then
        begin
        d[p^.n]:=d[k]+p^.c;
        ok:=true;
        if chk[p^.n] = false then begin chk[p^.n]:= true; inc(ct); cod[ct]:=p^.n; end;
        end;
      p:=p^.a;
      end;
    j:=j+1;
    end;
  end;


if ok then writeln (g, 'Ciclu negativ!')
      else for i := 2 to n do if d[i]=maxlongint then write (g, '0 ') else write (g, d[i], ' ');

close (f); close (g);
end.