Program bellmanford;
 uses crt;
 const inf=1000000;
 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]:=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 (a[i].c+q[l].t<val[a[i].y])) then
                  begin
                    if (val[a[i].y]=inf) then
                     begin
                      q[r].k:=a[i].y;
                      q[r].t:=a[i].c+q[l].t;
                      inc(r);
                     end;
                     val[a[i].y]:=a[i].c+q[l].t;
                    end;

          end;

         for i:=1 to m do
          begin
            if (val[a[i].x]+a[i].c<val[a[i].y]) and (val[a[i].x]<>inf) then
              val[a[i].y]:=val[a[i].x]+a[i].c;
          end;

        inc(l);
       end;


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


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