program bellman_ford;
type natural=record
 nod:longint;
 cost:integer;
end;
var f,g:text;
    a:array of array of natural;
    c:array of longint;
    viz:array of 0..1;
    d:array of longint;
    n,m,x,y,z,i,wnod,wcost,ps,pi,nr:longint;

begin
 assign (f,'bellmanford.in'); reset (F);
 assign(g,'bellmanford.out'); rewrite (g);
 readln (f,n,m);
 setlength (a,n+1);
 setlength (d,n+1);
 setlength (c,n+1); setlength (viz,n+1);
 for i:=1 to n do
 begin
  setlength (a[i],1);
  if i<>1 then
   d[i]:=maxlongint;
 end;
 for i:=1 to m do
 begin
  readln (f,x,y,z);
  a[x,0].nod:=a[x,0].nod+1;
  setlength (a[x],length (a[x])+1);
  a[x,a[x,0].nod].nod:=y;
  a[x,a[x,0].nod].cost:=z;
 end;
 ps:=0; pi:=1;
 c[1]:=1;   c[ps]:=1;
 while ps<pi do
 begin
 ps:=ps+1;
 if ps=500000 then
 begin
  write (g,'Ciclu negativ!');
  close (F); close (G);
  exit;
 end;
  nr:=c[ps];
  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;
   d[wnod]:=d[nr]+wcost;
  end;
  end;
  end;
 for i:=2 to n do
  if d[i]=maxlongint then
   write (g,'0 ')
  else
  write (g,d[i], ' ');
 writeln (G);
 close (F); close (G);
end.