Program bellmanford;
 uses crt;
 const inf=100000;
 type  drum=record
     x,y,c:longint;
      end;
    vector=array[1..250001] of drum;
     coada=record
      k,t:longint;
       end;

   var a:vector;
    q:array[1..500000] of coada;
    val:array[1..50001] of longint;
     i,j,n,m,l,r:longint;
     f,g:text;

BEGIN
 clrscr;
    assign(f,'bellmanford.in'); reset(f);
    assign(g,'bellmanford.out'); rewrite(g);
      {citirea}
      read(f,n,m);
       for i:=1 to m do
        read(f,a[i].x,a[i].y,a[i].c);



     {initialization}
      for i:=1 to n do
       val[i]:=inf;


      val[1]:=-inf;
      l:=1; r:=2; q[l].k:=1; q[l].t:=0;

    {rezolvare}
      while (l<r) do
       begin
         for i:=1 to m do
          begin
            if ((a[i].x=q[l].k) and (a[i].c+q[l].t<val[a[i].y])) then
                   begin
                     val[a[i].y]:=a[i].c+q[l].t;
                      q[r].k:=a[i].y;
                      q[r].t:=val[a[i].y];
                      inc(r);
                    end;

          end;
       {   writeln(q[l].k);
         for j:=1 to r-1 do
          writeln(q[j].k,' : ',q[j].t,' ');
          writeln;
          if readkey='q' then halt;
                    clrscr;  }

        inc(l);
       end;


    for i:=2 to n do
     write(g,val[i],' ');


    close(f); close(g);
END.