Program belmanford;
 type lista=^celula;
       celula=record
        nod,c:longint;
        next:lista;
        end;
var graf:array [1..50000] of lista;
    v:lista;
    b:array [1..50000] of boolean;
    st,cost,st1:array [1..50000] of longint;
    i,j,n,m,lev,x,y,c,nod:longint;
    fi,fo:text;
begin
 assign(fi,'bellmanford.in');
  assign(fo,'bellmanford.out');
 reset(fi); rewrite(fo); readln(fi,n,m);
  for i:=1 to m do begin
                    readln(fi,x,y,c);
                    new(v); v^.nod:=y; v^.c:=c; v^.next:=graf[x]; graf[x]:=v;
                    end;
  for i:=1 to n do cost[i]:=10000000;
   cost[1]:=0; b[1]:=true; lev:=1; st[lev]:=1; i:=1;
  while (lev>0) and (i<100000) do begin
   nod:=st[lev]; dec(lev); b[nod]:=false;
    v:=graf[nod];   inc(i);
     while v<>nil do begin
      if (cost[v^.nod]>cost[nod]+v^.c) then begin
                                          cost[v^.nod]:=cost[nod]+v^.c;
                                          if b[v^.nod]=false then begin
                                                              inc(lev);
                                                              st[lev]:=v^.nod;
                                                              b[v^.nod]:=true;
                                                              end;
                                           end;
       v:=v^.next;
      end;
               end;
   if lev>0 then write(fo,'Ciclu negativ!')
   else for i:=2 to n do write(fo,cost[i],' ');
  close(fo);
end.