Program belmanford;
 type lista=^celula;
       celula=record
        nod,c:longint;
        next:lista;
        end;
var graf:array [1..50000] of lista;
    v,last,r,vf:lista;
    ok:boolean;
    b1,b2:array [1..1 shl 17] of char;
    b:array [1..50000] of boolean;
    cost,nr:array [1..50000] of longint;
    i,j,n,m,x,y,c,nod:longint;
    fi,fo:text;
begin
 assign(fi,'bellmanford.in');
  assign(fo,'bellmanford.out');
 settextbuf(fi,b1); settextbuf(fo,b2);
 reset(fi); rewrite(fo); readln(fi,n,m);
  for i:=1 to m do begin
                    readln(fi,x,y,c);
                    new(v); v^.nod:=y; v^.c:=c; v^.next:=graf[x]; graf[x]:=v;
                    end;
  for i:=1 to n do cost[i]:=10000000;
   cost[1]:=0; b[1]:=true; new(vf); vf^.nod:=1; vf^.next:=nil; last:=vf; nr[1]:=1;
  while vf<>nil do begin
   nod:=vf^.nod; b[nod]:=false;
    v:=graf[nod];
     while v<>nil do begin
      if (cost[v^.nod]>cost[nod]+v^.c) then begin
                                          cost[v^.nod]:=cost[nod]+v^.c;
                                          if b[v^.nod]=false then begin
                                                              new(r); r^.nod:=v^.nod; r^.next:=nil;
                                                              last^.next:=r; last:=r;
                                                              b[v^.nod]:=true;
                                                              inc(nr[v^.nod]);
                                                              if nr[v^.nod]>n-1 then begin ok:=true; break; end;
                                                              end;
                                           end;
                   v:=v^.next;
                    end;
   if ok then break;
    r:=vf; vf:=vf^.next; {dispose(r);}
               end;
   if vf<>nil then write(fo,'Ciclu negativ!')
   else for i:=2 to n do write(fo,cost[i],' ');
  close(fo);
end.