program Dijkstra_cu_bellman;
var f,g:text;
    n,m,z,x,i,j,k,cost,p,u,nod:longint;
    t:array[0..2,1..250001] of longint;
    coada:array[1..500001] of longint;
    start,d:array[1..50000] of longint;
    viz:array[1..50001] of byte;
    bufin,bufout:array[1..66000] of byte;
begin
        assign(f,'dijkstra.in'); reset(f);
        assign(g,'dijkstra.out'); rewrite(g);
        settextbuf(f,bufin);
        settextbuf(f,bufout);
        //citire graf orientat
        readln(f,n,m);
        k:=0;
        for x:=1 to m do
                begin
                  readln(f,i,j,cost);
                  inc(k);
                  t[0,k]:=j;
                  t[1,k]:=start[i];
                  start[i]:=k;
                  t[2,k]:=cost;
                end;
        //initializare
        for i:=2 to n do
                d[i]:=maxlongint;
        d[1]:=0;
        p:=1; u:=1;
        coada[1]:=1;
        while (p <= u) do
                begin
                  nod:=coada[p];
                  viz[nod]:=0;
                  z:=start[nod];
                  while (z <> 0) do
                        begin
                          if d[nod]+t[2,z] < d[t[0,z]] then
                                begin
                                  d[t[0,z]]:=d[nod]+t[2,z];
                                  if viz[t[0,z]] = 0 then
                                        begin
                                          inc(u);
                                          coada[u]:=t[0,z];
                                          viz[t[0,z]]:=1;
                                        end;
                                end;
                          z:=t[1,z];
                        end;
                  inc(p);
                end;
        //afisare
        for i:=2 to n do
                if d[i] < maxlongint then
                        write(g,d[i],' ')
                        else
                        write(g,'0',' ');

        close(f); close(g);
end.