program bellman;
var f,g:text;
    n,m,z,x,i,j,k,cost,p,u,nod,y,v:longint;
    t:array[0..2,1..250001] of longint;
    start,viz,fr,d:array[1..50001] of longint;
    coada:array[1..500000] of longint;
    ok:boolean;
begin
        assign(f,'bellmanford.in'); reset(f);
        assign(g,'bellmanford.out'); rewrite(g);
        readln(f,n,m);
        k:=0;
        for x:=1 to m do
                begin
                readln(f,i,j,cost);
                inc(k);
                t[0,k]:=j;
                t[1,k]:=start[i];
                start[i]:=k;
                t[2,k]:=cost;
                end;

        //INITIALIZARE
        for i:=2 to n do
                d[i]:=maxlongint;
        //bellman ford
        p:=1; u:=1;
        ok:=true;
        coada[1]:=1;
        d[1]:=0;
        while (p <= u) and (ok = true) do
                begin
                nod:=coada[p];
                viz[nod]:=0;
                z:=start[nod];
                //cat timp am noduri adiacente
                while (z <> 0) and (ok = true) do
                        begin
                        if d[nod]+t[2,z] < d[t[0,z]] then
                                begin
                                d[t[0,z]]:=d[nod]+t[2,z];
                                if viz[t[0,z]] = 0 then
                                        begin
                                        inc(u);
                                        coada[u]:=t[0,z];
                                        fr[t[0,z]]:=fr[t[0,z]]+1;
                                        viz[t[0,z]]:=1;
                                        end;
                                end;
                        if fr[t[0,z]] = n then
                                ok:=false;
                        z:=t[1,z];
                        end;
                inc(p);
                end;
        //afisare
        if ok then
                begin
                for i:=2 to n do
                        if d[i] < maxlongint then
                                write(g,d[i],' ')
                        else
                                write(g,'0',' ')
                end
        else
                begin
                write(g,'Ciclu negativ!');
                end;
        close(f); close(g);

end.