type csucs = record
      tav,pred:longint;
     end;
     el = record
      a,b,c:longint;
     end;
     csucsok = array[1..50005] of csucs;
     elek = array[1..250050] of el;

var v:csucsok;
    uv:elek;
    i,n,m:longint;
    p:boolean;
    f:text;

function BellmanFord(var v:csucsok; n:longint; var uv:elek; m,s:longint):boolean;
var i,j:longint;
    ok:boolean;
begin

 { ... inicializalas ... }
 for i := 1 to n do begin
  if i = s then v[i].tav := 0
  else v[i].tav := MAXLONGINT;
  v[i].pred := 0;
 end;

 { ... kereses ... }
 for i := 1 to n-1 do
  for j := 1 to m do
   if v[uv[j].a].tav + uv[j].c < v[uv[j].b].tav then begin
    v[uv[j].b].tav := v[uv[j].a].tav + uv[j].c;
    v[uv[j].b].pred := uv[j].a;
   end;

 { ... negativ ciklus ... }
 ok := true;
 for i := 1 to m do
  if v[uv[j].a].tav + uv[j].c < v[uv[j].b].tav then begin
   ok := false;
   break;
  end;

 BellmanFord := ok;

end;

begin
assign(f,'bellmanford.in');
reset(f);
readln(f,n,m);
for i := 1 to m do
 readln(f,uv[i].a,uv[i].b,uv[i].c);
close(f);

p := BellmanFord(v,n,uv,m,1);

assign(f,'bellmanford.out');
rewrite(f);
if p = false then write(f,'Ciclu negativ!')
             else for i := 2 to n do write(f,v[i].tav,' ');
close(f);

end.