program bellman_ford;
type natural=record
nod,cost:longint;
end;
var n,m,i,x,y,z,wnod,wcost,ps,pi,nr:longint;
    a:array of array of natural;
    d,viz,c:array[1..1000000] of longint;
    f,g:text;
    intrare,iesire:array[1..65000] of byte;
begin
assign(f,'bellmanford.in');  reset(f);   settextbuf(f,intrare);
assign(g,'bellmanford.out'); rewrite(g); settextbuf(g,iesire);
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;
for i:=2 to n do d[i]:=maxlongint;
ps:=0; pi:=1; c[1]:=1;
while ps<pi do
  begin
  ps:=ps+1;
  nr:=c[ps];
  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
                                 pi:=pi+1;
                                 c[pi]:=wnod;
                                 viz[wnod]:=viz[wnod]+1;
                                 d[wnod]:=d[nr]+wcost;
                                 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
 if d[i]=maxlongint then write(g,0,' ')
                    else write(g,d[i],' ');
close(f);close(g);
end.