const inf=10000;
var f:text;
c:array[1..10000,1..10000] of integer;
d:array[1..10000] of int64;
tata:array[1..10000] of integer;
n,i,j,m,x,y,cost,x0,k:longint;
ok:boolean;
procedure citire;
begin
assign(f,'bellmanford.in');reset(f);
read(f,n,m);
for i:=1 to n do
        for j:=1 to n do
                if i=j then c[i,j]:=0
                        else c[i,j]:=inf;
for i:=1 to m do
        begin
        read(f,x,y,cost);
        c[x,y]:=cost;
        end;
close(f);
x0:=1;
end;
procedure scrie;
begin
assign(f,'bellmanford.out');rewrite(f);
if ok then writeln(f,'Ciclu negativ!')
else
for i:=2 to n do
        write(f,d[i],' ');
close(f);
end;
procedure bellman;
begin
for i:=1 to n do
        begin
          tata[i]:=0;
          d[i]:=inf;
        end;
d[x0]:=0;
for i:=1 to n do
        begin
        ok:=false;
        for j:=1 to n do
                for k:=1 to n do
                        if (d[j]<>inf) and (c[j,k]<>inf) then
                          if (d[k]>d[j]+c[j,k]) then
                                begin
                                  d[k]:=d[j]+c[j,k];
                                  tata[k]:=j;
                                  ok:=true;
                                end;
        end;
end;
begin
citire;
bellman;
scrie;
end.