program bellman_ford;
var f,g:text;
    n,m,k,x,y,v,i,p,u,z,nod:longint;
    t:array[0..2,1..250001] of longint; //liste de adiacenta + cost
    start,d,coada,fr:array[1..250001] of longint;
    viz:array[1..250001] of byte; // = 1, daca nodul i se afla in coada !!
    ok:boolean;
begin
    assign(f,'bellmanford.in'); reset(f);
    assign(g,'bellmanford.out'); rewrite(g);
    readln(f,n,m); k:=0;
    //CITIRE
    for i:=1 to m do
       begin
          readln(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; //initializam distantele de la nodul sursa la celelalte noduri
    d[1]:=0;
    p:=1; u:=1;
    coada[1]:=1;
    ok:=true;
    while (p <= u) and (ok = true) do //cat timp am elemente in coada si nu am ciclu negativ
       begin
         nod:=coada[p]; viz[nod]:=0; z:=start[nod];
         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-1 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],' ')
       end
       else
       write(g,'Ciclu negativ!');
   close(f); close(g);
end.