program bellmanford;
  const nmax=50000;
        inf=1 shl 30;
  type lista=^celula;
        celula=record
             info:longint;
             cost:longint;
             pred:lista;
             end;
  var a:array[1..nmax] of lista;
      c,d,viz:array[1..10*nmax] of longint;
      n,m,i,x,y,z,p,u:longint;
      r:lista;
      ciclu_negativ:boolean;
      bufin,bufout:array[1..1 shl 16] of byte;

  begin
    assign(input,'dijkstra.in');
    assign(output,'dijkstra.out');
    reset(input);
    rewrite(output);
    settextbuf(input,bufin);
    settextbuf(output,bufout);
    readln(n,m);
    for i:=1 to m do
     begin
       readln(x,y,z);
       new(r);
       r^.info:=y;
       r^.cost:=z;
       r^.pred:=a[x];
       a[x]:=r;
     end;
    for i:=1 to n do d[i]:=inf;
    d[1]:=0;
    c[1]:=1;
    p:=1;u:=1;
    while (p<=u)and (not ciclu_negativ) do begin
       r:=a[c[p]];
       while r<>nil do
         begin
           if r^.cost+d[c[p]]<d[r^.info]
            then begin
                 inc(viz[r^.info]);
                 if viz[r^.info]=n then
                     ciclu_negativ:=true;
                 d[R^.info]:=r^.cost+d[c[p]];
                 inc(u);
                 c[u]:=r^.info;
              end;
            r:=r^.pred;
           end;
         inc(p);
       end;
    if ciclu_negativ then writeln('Ciclu negativ!') else
    for i:=2 to n do
     if d[i]=inf then write(0,' ') else write(d[i],' ');
    close(output);
  end.