program bellman1;
const maxnod = 50001;
      maxmuchii = 250001;
var f, g:text;
    n, m, k, i, j, cost, p, u, z, nod:longint;
    t:array[0..2,1..maxmuchii] of longint;
    viz:array[1..maxnod] of boolean;
    start,d:array[1..maxnod] of longint;
    coada:array[1..10*maxmuchii] of longint;
    bufin,bufout:array[1..1 shl 17] of char;
begin
        assign(f,'dijkstra.in'); reset(f);
        assign(g,'dijkstra.out'); rewrite(g);
        //---------------------------------
        settextbuf(f,bufin); settextbuf(f,bufout);
        //---------------------------------
        readln(f, n, m);
        for k := 1 to m do
                begin
                  readln(f, i, j, cost);
                  t[0, k] := j;
                  t[1, k] := start[i];
                  start[i] := k;
                  t[2 ,k] := cost;
                end;
        //--------------------------------
        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] := false;
                  z := start[nod];
                  while z <> 0 do
                        begin
                          if d[nod] + t[2 ,z] < d[t[0, z]] then
                                begin
                                  d[t[0 ,z]] := t[2, z] + d[nod];
                                  if not viz[t[0,z]] then
                                        begin
                                          inc(u);
                                          coada[u] := t[0, z];
                                          viz[t[0,z]] := true;
                                        end;
                                end;
                          z := t[1, z];
                        end;
                  inc(p);
                end;
        //------------------------------
        for i := 2 to n do
                if d[i] < maxlongint then write(g, d[i], ' ')
                                     else write(g, '0', ' ');

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