const nodmax=50002;
      mucmax=250002;
      inf=2000000000;
type muchie=record
    X,Y,cost:longint;
    end;
var e:array [1..mucmax] of muchie;
    d:array [1..nodmax] of longint;
    i,j,m,n:longint;
    ok:boolean;
begin
    assign(input,'bellmanford.in');
    reset(input);
    assign(output,'bellmanford.out');
    rewrite(output);
    readln(n,m);
    for i := 2 to n do d[i]:=inf;


    for i := 1 to m do
     read(e[i].x,e[i].y,e[i].cost);

    
    repeat
        ok:=false;
        for i := 1 to m  do
                If d[e[i].y]>d[e[i].x]+e[i].cost then  begin
                        d[e[i].y]:=d[e[i].x]+e[i].cost;
                        ok:=true;
                        end;
        j:=j+1;                                         
    until (ok=false) or (j=800);
    if j=800 then write('Ciclu negativ!')
    else 
    for i:=2 to n  do write(d[i],' ');

    close(input);
    close(output);

end.