program repet;
const Nmax = 50005;
      Mmax = 250005;
var f, g:text;
    bufin, bufout:array[1..1 shl 16] of byte;
    start, d:array[1..Nmax] of longint;
    coada:array[1..10*Nmax] of longint;
    viz:array[1..Nmax] of boolean;
    i, k, n, m, p, u, z, nod:longint;
    t:array[0..2, 1..Mmax] of longint;
begin
   assign(f, 'dijkstra.in'); reset(f);
   assign(g, 'dijkstra.out'); rewrite(g);
   readln(f, n, m);
   for k := 1 to m do
      begin
         readln(f, i, t[0, k], t[2, k]);
         t[1, k] := start[i];
         start[i] := k;
      end;
   d[1] := 0;
   for i := 2 to n do d[i] := maxlongint;
   p := 1; u := 1;
   coada[p] := 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]] := d[nod] + t[2, z];
                     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, '0 ') else
                                write(g, d[i],' ');
   close(f); close(g);
end.