program kk;
type ref=^inr;
     inr=record
          nr:longint;
          cost:longint;
          adr:ref;
         end;
var f:text;
    lista,u:array[1..50000] of ref;
    q:ref;
    coada:array[1..1500000] of longint;
    lung:array[1..50000] of longint;
    viz,v:array[1..50000] of 0..1;

    n,m,pc,uc,i,a,b,c:longint;

procedure adaug_in_lista(x,y,z:longint);
begin
   new(q);
   q^.nr:=y;
   q^.adr:=nil;
   q^.cost:=z;
  if lista[x]=nil then begin
                         lista[x]:=q;
                         u[x]:=q;
                       end
                  else begin
                        u[x]^.adr:=q;
                        u[x]:=q;
                       end;
end;

begin
assign(f,'dijkstra.in');
reset(f);
readln(f,n,m);
for i:=1 to m do
  begin
     readln(f,a,b,c);
     adaug_in_lista(a,b,c);
  end;
lung[1]:=0;
for i:=2 to n do lung[i]:=2000000000;
pc:=1;
uc:=1;
viz[1]:=1;
coada[pc]:=1;
while pc<=uc do
  begin
    q:=lista[coada[pc]];
    while q<>nil do
      begin
       if viz[q^.nr]=0 then begin
                               uc:=uc+1;
                               viz[q^.nr]:=1;
                               v[q^.nr]:=1;
                               coada[uc]:=q^.nr;
                               if lung[coada[pc]]+q^.cost<lung[q^.nr] then lung[q^.nr]:=lung[coada[pc]]+q^.cost;
                             end;
       q:=q^.adr;
      end;
    viz[pc]:=0;
    pc:=pc+1;
  end;
close(f);
assign(f,'dijkstra.out');
rewrite(f);
for i:=2 to n do
  if v[i]=1 then write(f,lung[i],' ')
            else write(f,0,' ');
close(f);
end.