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;

//v-graful
//d-costul minim de la varful 1 la varful i
//chk-folosit pentru coada, a.i. vecotrul cod sa nu iasa din 50000 elemente
//cod- coada. cod[x, 0] numarul din elemente din coada
//sw1, sw2 - switchuri. Lucrez cu 2 cozi care se schimba intre ele dupa fiecare incrementare a lui i

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;
  for j := 1 to cod[sw1, 0] do chk[cod[sw1, j]]:=false;    //Reinitializarea vectorului chk varianta optimizata de la fillchar
  sw1 := i mod 2; sw2:= (i+1) mod 2;                       //Schimbarea switch-urilor
  j:=1;
  cod[sw1, 0]:=0;                                          //Initializarea numarului de elemente din coada
  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     //Daca se gaseste drum de cost mai mic
        begin
        d[p^.n]:=d[k]+p^.c;
        ok:=true;                             //Daca ciclul este negativ, se va gasi o muchie de cost mai mic la fiecare i
        if chk[p^.n] = false then
          begin
          chk[p^.n]:= true; inc(cod[sw1, 0]); cod[sw1, cod[sw1, 0]]:=p^.n;  //Adaugarea la coada
          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.