program bellmanford;
var t:array[1..3,1..50000] of longint;
    c:array[1..500000] of longint;
    d,start,fr:array[1..50000] of longint;
    viz:array [1..50000] of 0..1;
    n,m:longint;
    f,g:text;
procedure citire;
var i,j,k,c:longint;
  begin
    assign(f,'bellmanford.in');
    assign(g,'bellmanford.out');
    reset(f);
    rewrite(g);
    readln(f,n,m);
    for k:=1 to m do
      begin
        readln(f,i,j,c);
        t[1,k]:=j;
        t[2,k]:=start[i];
        t[3,k]:=c;
        start[i]:=k;
      end;
  end;
procedure bellman(sursa:longint);
var i,st,sf,p,nod:longint;
    ok:boolean;
  begin
    for i:=2 to n do
      d[i]:=maxlongint;
    d[sursa]:=0;
    st:=0;
    sf:=1;
    c[1]:=sursa;
    ok:=true;
    while (st<sf) and (ok=true) do
      begin
       inc(st);
       nod:=c[st];
       viz[nod]:=0;
       p:=start[nod];
       while (p<>0) and (ok=true) do
         begin
           if d[nod]+t[3,p]<d[t[1,p]] then
                                      begin
                                        d[t[1,p]]:=d[nod]+t[3,p];
                                        if viz[t[1,p]]=0 then
                                                         begin
                                                           inc(sf);
                                                           c[sf]:=t[1,p];
                                                           inc(fr[t[1,p]]);
                                                           viz[t[1,p]]:=1;
                                                         end;
                                      end;
           if fr[t[1,p]]>n-1 then
                             ok:=false;
           p:=t[2,p];
         end;
      end;
    if ok=true then
                for i:=2 to n do
                  write(g,d[i],' ')
                  else
                  writeln(g,'Ciclu negativ!');
  end;
begin
  citire;
  bellman(1);
  close(f);
  close(g);
end.