program p1;
type lista=^celula;
     celula=record
     info:longint;
     cost:integer;
     next:lista;
            end;
var a:array[0..50000] of lista;
    coada,viz:array[0..1000000] of longint;
    d:array[0..50000] of int64;
    f,g:Text;
    b1,b2:array[0..1 shl 17 ] of char;
    i,n,j,k,u,m,x,y,c,i_C,sf_C:longint;
    v:lista;
    p:boolean;
    nod:word;
 
procedure add(x,cost1:longint; var p:lista);
var r:lista;
begin
 new(R);
 r^.info:=x;
 r^.cost:=cost1;
 r^.next:=p;
 p:=r;
end;
 
 
begin
assign(f,'bellmanford.in');reset(F);
assign(G,'bellmanford.out');rewrite(G);
 settextbuf(f,b1);
 settextbuf(g,b2);
 readln(f,n,m);
 for i:=1 to m do begin
        readln(f,x,y,c);
        add(y,c,a[x]);
                end;
 coada[1]:=1;
 i_c:=1;
 sf_c:=1;
 p:=true;
 d[1]:=0;viz[1]:=1;
 for i:=2 to n do d[i]:=2000000000;
 {for i:=1 to n do begin  21
        v:=a[i];     write(g,i,':');
        while v<>nil do begin
                write(g,v^.info,' ');
                v:=v^.next;
                        end;
        writeln(G);
                end;  }
 while (i_c<=sf_C) and p do begin
                v:=a[coada[i_C]];
                while v<>nil do begin
                     if d[coada[i_C]]+v^.cost<d[v^.info] then begin
                                        inc(viz[v^.info]);
                                        if viz[v^.info]=n then begin
                                                        p:=false;
                                                        break;
                                                                end;
                                        d[v^.info]:=d[coada[i_C]]+v^.cost;
                                        inc(sf_C);
                                        coada[sf_C]:=v^.info;
                                        end;
                     v:=v^.next;
                     end;
                     inc(i_C);
                        end;
 if not p then writeln(g,'Ciclu negativ!')
        else for i:=2 to n do write(G,d[i],' ');
close(F);
close(G);
end.