program bellman;
type pointer=^nod;
     nod=record
        nr,cost:integer;
        urm:pointer;
     end;

var prim,ult:array[0..50001] of pointer;
    n,m,x,i,j,y,z:longint;
    c:pointer;
    ok:boolean;
    d:array[0..50001]of longint;
    f:text;

procedure adauga(a,b,cost:integer);
var c:pointer;
begin
 if prim[a]=nil then begin
  new(prim[a]);
  prim[a]^.nr:=b;
  prim[a]^.cost:=cost;
  prim[a]^.urm:=nil;
  ult[a]:=prim[a];
 end
 else begin
  new(c);
  c^.nr:=b;
  c^.cost:=cost;
  c^.urm:=nil;
  ult[a]^.urm:=c;
  ult[a]:=c;
 end;
end;

procedure parcurge(a:integer);
var c:pointer;
begin
 c:=prim[a];
 while c<>nil do begin
  if d[a]+c^.cost<d[c^.nr] then d[c^.nr]:=d[a]+c^.cost;
  c:=c^.urm;
 end;
end;

begin
 assign(f,'bellmanford.in'); reset(f);
  readln(f,n,m);
  for i:=1 to m do begin
   readln(f,x,y,z);
   adauga(x,y,z);
  end;
 close(f);

 for i:=1 to n do d[i]:=maxint;
 d[1]:=0;

  for j:=1 to n-1 do parcurge(j);

 ok:=false;
 for i:=1 to n do begin
  c:=prim[i];
  while c<>nil do begin
   if d[i]+c^.cost<d[c^.nr] then ok:=true;
   c:=c^.urm;
  end;
 end;

 assign(f,'bellmanford.out'); rewrite(f);
 if ok=false then begin
  for i:=2 to n do begin
   write(f,d[i],' ');
  end;
 end else write(f,'Ciclu negativ!');
 close(f);

end.