Program bellmann;
const infinit=10000005;
type lista=^celula;
     celula=record
            nod,c:longint;
            next:lista;
            end;
     vect=array[0..50005] of longint;
     vectbool=array[0..50005] of boolean;
var i,n,m,c,x,y,nod:longint;
    nr,cost:vect; b:vectbool;
    q,last,r,vf:lista; ok:boolean;
    graf:array[0..50005] of lista;
    f,g:text;
    intrare,iesire:array[1..300000]of char;
begin
assign(f,'bellmanford.in'); reset(f);  settextbuf(f,intrare);
assign(g,'bellmanford.out'); rewrite(g); settextbuf(g,iesire);
readln(f,n,m);
for i:=1 to n do begin
                 cost[i]:=infinit;
                 graf[i]:=nil;
                 end;
for i:=1 to m do
   begin
   readln(f,x,y,c);
   new(q); q^.nod:=y; q^.c:=c; q^.next:=graf[x]; graf[x]:=q;
   end;
cost[1]:=0; b[1]:=true;  nr[1]:=1;
new(vf); vf^.nod:=1; vf^.next:=nil; last:=vf;
while vf<>nil do
  begin
  nod:=vf^.nod;
  b[nod]:=false;
  q:=graf[nod];
  while q<>nil do
    begin
    if (cost[q^.nod]>cost[nod]+q^.c) then
                                          begin
                                          cost[q^.nod]:=cost[nod]+q^.c;
                                          if b[q^.nod]=false then begin
                                                                  new(r); r^.nod:=q^.nod; r^.next:=nil;
                                                                  last^.next:=r; last:=r;
                                                                  b[q^.nod]:=true;
                                                                  inc(nr[q^.nod]);
                                                                  if nr[q^.nod]>n-1 then begin ok:=true; break; end;
                                                                  end;
                                          end;
    q:=q^.next;
    end;
  if ok then break;
  r:=vf; vf:=vf^.next;
  end;
if vf<>nil then write(g,'Ciclu negativ!')
           else for i:=2 to n do write(g,cost[i],' ');
close(f); close(g);
end.