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[0..1, 0..50000] of longint;
    buf1, buf2:array [1..1 shl 17] of char;
    m, n, i, j, k, x, y, c:longint;
    sw1, sw2:integer;
    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[0, 1]:=1;  cod[0, 0]:=1;
for i := 1 to n do
  begin
  ok:=false;
//  fillchar (chk, n+1, false);
  sw1 := i mod 2; sw2:= (i+1) mod 2;
  j:=1;
  cod[sw1, 0]:=0;
  while j <= cod[sw2, 0] do
    begin
    k:=cod[sw2, 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(cod[sw1, 0]); cod[sw1, cod[sw1, 0]]:=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.