program dffd;
type e=record
    nod,cost:longint;
    end;
    var f,g:text;
    n,m,x,y,z,i,pi,ps,j,nr,wnod,wcost:longint;
    a:array of array of e;
    q,d,viz:array[1..10000000] of longint;
    ok:boolean;
begin
assign(f,'bellmanford.in'); reset(f);
assign(g,'bellmanford.out'); rewrite(g);
readln(f,n,m);
setlength(a,n+1);
for i:=1 to n do
  setlength(a[i],1);
  ok:=true;
  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;
    pi:=1;
    ps:=1;
    q[pi]:=1;
    d[1]:=0;
    for i:=2 to n do
      d[i]:=maxlongint;
        while ps<=pi do
          begin
            nr:=q[ps];
            ps:=ps+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;
                      pi:=pi+1;
                      q[pi]:=wnod;
                      viz[wnod]:=viz[wnod]+1;
                        if viz[wnod]>n then
                          begin
                            ok:=false;
                            break;
                          end;
                    end;
                end;
          end;
        if ok=false then
          write(g,'Ciclu negativ!')
          else
            for i:=2 to n do
              begin
                write(g,d[i],' ');
              end;
close(f);
close(g);
end.