Program bellmanford;
 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;
    parcurs:array[1..50001] of boolean;
    val:array[1..50001] of longint;
     i,j,n,m,l,r:longint;
     f,g:text;

BEGIN
    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);

       if n=1 then write(g,'Ciclu negativ!')
        else begin

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

      parcurs[1]:=true;
      val[1]:=0;
      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 (not(parcurs[a[i].y]))) then
              begin
                 if (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:=a[i].c+q[l].t;
                     inc(r);
                   end;
              end;

          end;

        parcurs[q[l].k]:=true;
        inc(l);
       end;


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

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