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

var v:array [1..50000] of muchie;         //Graful
    r:array [1..50000] of longint;        //Rezultatul final (distanta de la nodul 1 la nodul i
    q:array [0..1, 0..50000] of longint;  //Cele doua cozi se interschimba cu sw1 si sw2
    viz:array [1..50000] of boolean;      //Pentru a nu baga de doua ori in coada acelasi element
    p:muchie;
    i, j, n, m, sw1, sw2, x, y, z:longint;
    f, g:text;
    buf1, buf2:array [1.. 1 shl 17] of char;

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

//Citirea
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;

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

//Cat timp mai exista elemente in coada (stim ca nu putem avea ciclu negativ)
while q[sw1, 0]>0 do
  begin
  q[sw2, 0]:=0;                           //initializari
  for i := 1 to n do viz[i]:=false;

  for i := 1 to q[sw1, 0] do
    begin
    x:=q[sw1, i];                         //Ia varful din coada
    p:=v[x];
    while p <> nil do                     //verifica prin toti vecinii
      begin
      if r[x]+p^.c<r[p^.n] then           //Daca gasim drum mai ieftin
        begin
        r[p^.n]:=r[x]+p^.c;
        if viz[p^.n] = false then         //Adaugam in coada doar daca nu am adaugat inca
          begin
          viz[p^.n]:=true;
          inc (q[sw2, 0]);
          q[sw2, q[sw2, 0]]:=p^.n;        //q[sw2, 0] inseamna lungimea cozii
          end;
        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.