program repetbellman;
const Nmax = 50005;
      Mmax = 250005;
var f, g:text;
    bufin, bufout:array[1..1 shl 16] of byte;
    t:array[0..2, 1..Nmax] of longint;
    start, d, fr:array[1..Nmax] of longint;
    coada:array[1..10*Nmax] of longint;
    viz:array[1..Nmax] of boolean;
    i, n, m, k, p, u, nod, z:longint;
begin
   assign(f, 'bellmanford.in'); reset(f);
   assign(g, 'bellmanford.out'); rewrite(g);
   settextbuf(f, bufin); settextbuf(g, bufout);
   readln(f, n, m);
   for k := 1 to m do
       begin
          readln(f, i, t[0, k], t[2, k]);
          t[1, k] := start[i];
          start[i] := k;
       end;
   d[1] := 0;
   for i := 2 to n do d[i] := maxlongint;
   p := 1; u := 1;
   coada[p] := 1;
   while p <= u do
      begin
         nod := coada[p];
         viz[nod] := false;
         z := start[nod];
         while z <> 0 do
            begin
               if d[nod] + t[2, z] < d[t[0, z]] then
                  begin
                     d[t[0, z]] := d[nod] + t[2, z];
                     if not(viz[t[0, z]]) then
                        begin
                           inc(u);
                           coada[u] := t[0, z];
                           viz[t[0, z]] := true;
                           inc(fr[t[0, z]]);
                        end;
                  end;
               if fr[t[0, z]] = n then
                  begin
                     writeln(g, 'Ciclu negativ!');
                     close(f); close(g);
                     halt;
                  end;
               z := t[1, z];
            end;
         inc(p);
      end;
   for i := 2 to n do
      if d[i] = maxlongint then write(g, '0 ')
         else write(g, d[i],' ');
   close(f); close(g);
end.