program bellman_ford;
  var bufin,bufout:array [1..100000] of byte;
      n,m,i,j:longint;
      first,second,cost:array [1..250000] of longint;
      drum:array [1..50000] of longint;
      ok:boolean;

begin
  assign(input,'bellmanford.in');
  reset(input);
  settextbuf(input,bufin);
  assign(output,'bellmanford.out');
  rewrite(output);
  settextbuf(output,bufout);

  readln(n,m);
  for i:=1 to m do readln(first[i],second[i],cost[i]);
  for i:=1 to n do drum[i]:=-1;
  drum[1]:=0;
  for i:=1 to 1000 do
    for j:=1 to m do
      begin
        if (drum[first[j]]<>-1) and ((drum[second[j]]=-1)
            or(drum[first[j]]+cost[j]<drum[second[j]])) then
              drum[second[j]]:=drum[first[j]]+cost[j];
      end;

  ok:=true;
  for i:=1 to m do
    if drum[first[i]]+cost[i]<drum[second[i]] then ok:=false;
  if ok then
    for i:=2 to n do write(drum[i], ' ')
        else writeln('Ciclu negativ!');
  close(output);
end.