Program p1;
const limit=10000005;
type lista=^celula;
     celula=record
            nod,c:longint;
            next:lista;
            end;
var fi,fo:text; i,n,m,c,x,y,nod:longint;
    b1:array[0..50005] of char;  b:array[0..50005] of boolean;
    nr,cost:array[0..50005] of longint;
    q,last,r,vf:lista; ok:boolean;
    graf:array[0..50005] of lista;
 
begin
    assign(fi,'bellmanford.in'); reset(fi);
    assign(fo,'bellmanford.out'); rewrite(fo);
    settextbuf(fi,b1); readln(fi,n,m);
    for i:=1 to n do begin cost[i]:=limit; graf[i]:=nil; end;
 
    for i:=1 to m do begin
                     readln(fi,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(fo,'Ciclu negativ!')
               else for i:=2 to n do write(fo,cost[i],' ');
    close(fi); close(fo);
end.