const infile='bellmanford.in';
  outfile='bellmanford.out';
  maxn=50003;
  infinit=1000000000;
type nod=^pnod;
  pnod=record  vf:longint; urm:nod; end;
  coada=record  prim,ultim:nod; end;
  list=^vec;
  vec=record  inf,cost:longint; next:list; end;
var a:array[1..maxn]of list;
  inq,d:array[1..maxn]of longint;
  q:coada;
  n,m:longint;

 procedure citire;
 var i,j,c:longint;
   p:list;
 begin
   assign(input,infile); reset(input); readln(n,m);
   while(m>0)do begin
     readln(i,j,c); dec(m);
     new(p); p^.inf:=j; p^.cost:=c; p^.next:=a[i]; a[i]:=p;
     end;
   close(input);
 end;

 procedure pop;
 var r:nod;
 begin
   with q do begin
     r:=prim; prim:=prim^.urm;
     dispose(r);
     end;
 end;

 procedure push(x:longint);
 var r:nod;
 begin
   with q do
     if(prim=nil)then begin
       new(prim); prim^.vf:=x;
       prim^.urm:=nil; ultim:=prim
       end
     else begin
       new(r); r^.vf:=x; r^.urm:=nil;
       ultim^.urm:=r; ultim:=r;
       end;
 end;

 function BellmanFord:boolean;
 var p:list;
   x,i:longint;
   ok:boolean;
 begin
   for i:=2 to n do d[i]:=infinit;
   ok:=true;
   push(1);
   d[1]:=0; inq[1]:=1;
   while(q.prim<>nil)and(ok)do begin
     x:=q.prim^.vf;
     pop;
     p:=a[x];
     while(p<>nil)do begin
       if(d[p^.inf]>d[x]+p^.cost)then begin
         d[p^.inf]:=d[x]+p^.cost; push(p^.inf);
         inc(inq[p^.inf]);
         end;
       if(inq[p^.inf]>=n)then ok:=false;
       p:=p^.next;
       end;
     end;
   BellmanFord:=ok;
 end;

 procedure afisare;
 var i:longint;
 begin
   assign(output,outfile); rewrite(output);
   if BellmanFord then for i:=2 to n do write(d[i],' ')
   else write('Ciclu negativ!');
   close(output);
 end;

Begin
  citire; afisare;
End.