program bellman;
var t:array[0..2,1..500001] of longint;
    start,viz,fr,d:array[0..50000] of longint;
    cd:array[1..500001] of longint;
    ok:boolean;
    nod,st,sf,x,y,v,i,j,n,m,k,p:longint;
    bufin,bufout:array[1..750002] of byte;
    f,g:text;
begin
    assign(f,'bellmanford.in');
    reset(f);
    assign(g,'bellmanford.out');
    rewrite(g);
    settextbuf(f,bufin);
    settextbuf(g,bufout);
    readln(f,n,m);
    k:=0;
    for i:=1 to m do
       begin
           read(f,x,y,v);
           inc(k);
           t[0,k]:=y;
           t[1,k]:=start[x];
           start[x]:=k;
           t[2,k]:=v;
       end;
    for i:=2 to n do
        d[i]:=maxlongint;
    d[1]:=0;
    st:=0;
    sf:=1;
    cd[1]:=1;
    ok:=true;
    while (st<=sf) and (ok=true) do
        begin
             inc(st);
             nod:=cd[st];
             viz[nod]:=0;
             p:=start[nod];
             while (p<>0) and (ok=true) do
                begin
                    if d[nod]+t[2,p]<d[t[0,p]] then
                        begin
                            d[t[0,p]]:=d[nod]+t[2,p];
                            if viz[t[0,p]]=0 then
                               begin
                                  inc(sf);
                                  cd[sf]:=t[0,p];
                                  inc(fr[t[0,p]]);
                                  viz[t[0,p]]:=1;
                               end;
                        end;
                    if fr[t[0,p]]>=n then
                        ok:=false;
                    p:=t[1,p];
                end;
        end;
    if ok=true then
      begin
        for i:=2 to n do
            if d[i]<maxlongint then
                write(g,d[i],' ')
            else
                writeln(g,0,' ');
      end
    else
       write(g,'Ciclu negativ!');
    close(f);
    close(g);
end.