program bell;
type mi=record
nod,cost:longint; end;
var f,g:text;
n,m,i,j,st,sf,wnod,wcost,x,y,z,nr:longint;
q,viz,d:array[0..100000001] of longint;
a:array of array of mi;
begin
assign(f,'bellmanford.in'); reset(f);
assign(g,'bellmanford.out'); rewrite(g);
readln(f,n,m);
setlength(a,n+1,1);
   for i:=1 to m do
     begin
       readln(f,x,y,z);
       setlength(a[x],length(a[x])+1);
       a[x,0].nod:=a[x,0].nod+1;
       a[x,a[x,0].nod].nod:=y;
       a[x,a[x,0].nod].cost:=z;
     end;
   st:=1;sf:=1;q[st]:=1;
   d[1]:=0;
   for i:=2 to n do
     d[i]:=maxint;
     while st<=sf do
       begin
       nr:=q[st];
       st:=st+1;
       viz[nr]:=viz[nr]+1;
           for i:=1 to a[nr,0].nod do
              begin
              wnod:=a[nr,i].nod; wcost:=a[nr,i].cost;
                 if d[wnod]>d[nr]+wcost then
                   begin
                   d[wnod]:=d[nr]+wcost;
                   viz[wnod]:=viz[wnod]+1;
                   sf:=sf+1;
                   q[sf]:=wnod;
                     if viz[wnod]>n then
                     begin
                       write(g,'Ciclu negativ!');
                       close(f); close(g); exit;
                     end;
                   end;
              end;
       end;
       for i:=2 to n do
         write(g,d[i],' ');
close(f);
close(g);
end.