type lista=^element;
     element=record
        edge,cost:word;
        next:lista;
        end;

const nmax=50001;
      inf=maxint;

var list:array[1..nmax] of lista;
    h,poz,d:array[1..nmax] of word;
    i,j,m,n,min,t:longint;
    p:lista;

procedure citire;
var a,b,c:longint;
begin
assign(input,'dijkstra.in');reset(input);
readln(n,m);
for i:=1 to m do
        begin
        readln(a,b,c);
        new(p);
        p^.cost:=c;
        p^.edge:=b;
        p^.next:=list[a];
        list[a]:=p;

        new(p);
        p^.cost:=c;
        p^.edge:=a;
        p^.next:=list[b];
        list[b]:=p;
        end;
close(input);
end;

procedure down(i,n:longint);
var tata,fiu,v:longint;
begin
v:=h[i];
tata:=i;
fiu:=i shl 1;
while fiu<=n do
        begin
        if fiu<n then
                if d[h[fiu]]>d[h[fiu+1]] then fiu:=fiu+1;
        if d[h[v]]>d[h[fiu]] then
                begin
                h[tata]:=h[fiu];
                poz[h[fiu]]:=tata;
                tata:=fiu;
                fiu:=fiu shl 1;
                end
                             else fiu:=n+1;
        end;
h[tata]:=v;
poz[h[tata]]:=tata;
end;

procedure up(i,n:longint);
var tata,fiu,aux:longint;
begin
fiu:=i;
tata:=i shr 1;
while (tata<>0) and (d[h[tata]]>d[h[fiu]]) do
        begin
        aux:=h[fiu];
        h[fiu]:=h[tata];
        h[tata]:=aux;

        poz[h[fiu]]:=tata;
        poz[h[tata]]:=fiu;

        tata:=tata shr 1;
        fiu:=tata;
        end;
end;

procedure create_h;
begin
for i:=1 to n do
        begin
        h[i]:=i;
        poz[i]:=i;
        d[i]:=inf;
        end;
d[1]:=inf+1;
p:=list[1];
while p<>nil do
        begin
        h[p^.edge]:=p^.cost;
        p:=p^.next;
        end;
end;

procedure dijkstra;
begin
create_h;

for i:=(n shl 1) downto 1 do
        down(i,n);
t:=n;
for i:=1 to n do
  begin
  min:=h[1];
  h[1]:=h[t];
  h[t]:=inf;
  t:=t-1;
  down(1,t);
  p:=list[min];
  while p<>nil do
          begin
          if d[h[p^.edge]]>d[min]+p^.cost then
                  begin
                  d[h[p^.edge]]:=d[min]+p^.cost;
                  up(poz[p^.edge],t);
                  end;
          p:=p^.next;
          end;
  end;
end;

procedure afisare;
begin
assign(output,'dijkstra.out');rewrite(output);
for i:=2 to n do
        if d[i]=inf then write(0,' ')
                    else write(d[i],' ');
close(output);
end;

begin {main}
citire;
dijkstra;
afisare;
end.