type muchie=^nod;
     nod=record c, n:integer; a:muchie; end;

var v:array [1..50000] of muchie;
    buf1, buf2:array [1.. 1 shl 17] of char;
    r:array [1..50000] of longint;
    q:array [0..1, 0..50000] of longint;
    p:muchie;
    i, j, n, m, sw1, sw2, x, y, z:longint;
    f, g:text;

begin
assign (f, 'dijkstra.in'); settextbuf (f, buf1); reset (f);
assign (g, 'dijkstra.out'); settextbuf (g, buf2); rewrite (g);

read (f, n, m);
for i := 1 to m do
  begin
  read (f, x, y, z);
  new (p); p^.n:=y; p^.c:=z; p^.a:=v[x]; v[x]:=p;
  end;

for i := 2 to n do r[i]:=maxlongint;
sw1:=0; sw2:=1; q[0, 1]:=1; q[0, 0]:=1;

while q[sw1, 0]>0 do
  begin
  q[sw2, 0]:=0;
  for i := 1 to q[sw1, 0] do
    begin
    x:=q[sw1, i];
    p:=v[x];
    while p <> nil do
      begin
      if r[x]+p^.c<r[p^.n] then
        begin
        r[p^.n]:=r[x]+p^.c;
        inc (q[sw2, 0]);
        q[sw2, q[sw2, 0]]:=p^.n;
        end;
      p:=p^.a;
      end;
    end;
  sw1:=sw1 xor 1;
  sw2:=sw2 xor 1;
  end;

for i := 2 to n do if r[i]=maxlongint then write (g, '0 ') else write (g, r[i], ' ');
close (f); close (g);
end.