type pnod=^nod;
     nod= record
          info:longint;
          cost:integer;
          urm:pnod;
          end;

const infinit=20000000;

var v:array[1..5001]of pnod;
d:array[1..5001]of longint;
circneg:boolean;
n,x,y:longint;
c:integer;
m,i:longint;

procedure add(var p:pnod; x:word; c:integer);
var q:pnod;
begin
new(q);
q^.info:=x;
q^.cost:=c;
q^.urm:=nil;
if p<>nil then q^.urm:=p;
p:=q;
end;

procedure bellmanford;
var coada:array[1..20000]of longint;
apare:array[1..5001]of longint;
p,u:longint;
nod:longint;
q:pnod;

begin
coada[1]:=1;
p:=1; u:=1;
fillchar(apare,sizeof(apare),0);
apare[1]:=1;
circneg:=false;
while (p<=u)and(not circneg) do begin
      nod:=coada[p];
      q:=v[nod];
      while q<>nil do begin
            if d[nod]+q^.cost<d[q^.info] then begin
               inc(apare[q^.info]);
               if apare[q^.info]=n then circneg:=true;
               d[q^.info]:=d[nod]+q^.cost;
               inc(u);
               coada[u]:=q^.info;
            end;
            q:=q^.urm;
      end;
      inc(p);
end;
end;

begin
assign(input,'bellmanford.in');
reset(input);
assign(output,'bellmanford.out');
rewrite(output);
read(n,m);
for i:=1 to m do begin
    read(x,y,c);
    add(v[x],y,c);
end;

d[1]:=0;
for i:=2 to n do d[i]:=infinit;

bellmanford;

if circneg then write('Ciclu negativ!')
           else
               for i:=2 to n do write(d[i],' ');
close(output);
end.