type muchie=record
     st,dr,cost:longint;
     end;
var v:array [1..250000] of muchie;
    d:array [1..50000] of longint;
    n,m,i,j:longint;
    f,g:text;
begin
assign(f,'bellmanford.in');reset(f);
readln(f,n,m);
for i:=1 to m do
    readln(f,v[i].st,v[i].dr,v[i].cost);
close(f);
fillchar(d,sizeof(d),127);
d[1]:=0;
for i:=1 to n do
    for j:=1 to m do
        if d[v[j].dr]>d[v[j].st]+v[j].cost then
           d[v[j].dr]:=d[v[j].st]+v[j].cost;
assign(g,'bellmanford.out');rewrite(g);
for i:=1 to m do
    if d[v[i].dr]>d[v[i].st]+v[i].cost then
       begin
       write(g,'Ciclu negativ!');
       close(g);
       halt
       end;
for i:=2 to n do
    write(g,d[i],' ');
close(g);
end.