type troll=record
      x,y,z:longint;
     end;

var a:array[1..300000] of troll;
    d:array[1..55000] of longint;
    i,n,m:longint;
    u:byte;
    bif,bof:array[1..1 shl 16] of char;

begin
 assign(input,'dijkstra.in');
 assign(output,'dijkstra.out');
 reset(input);
 rewrite(output);
 settextbuf(input,bif);
 settextbuf(output,bof);

  readln(n,m);
   for i:=1 to m do
    readln(a[i].x,a[i].y,a[i].z);
   for i:=2 to n do
    d[i]:=-1;

  u:=1;
   while u=1 do
    begin
     u:=0;
      for i:=1 to m do
       if (d[a[i].x]<>-1) and ((d[a[i].y]=-1) or (d[a[i].y]>d[a[i].x]+a[i].z)) then begin
                                                                                     d[a[i].y]:=d[a[i].x]+a[i].z;
                                                                                     u:=1;
                                                                                    end;
    end;

   for i:=2 to n do
    if d[i]=-1 then write('0 ')
               else write(d[i],' ');

 close(input);
 close(output);
{Totusi este trist in lume}
end.