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,q1,pc,uc:ref;
    lung:array[1..50000] of longint;
    viz:array[1..50000] of 0..1;
    n,m,i,a,b,c,cc: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]:=2140000000;

new(pc);
uc:=pc;
pc^.nr:=1;
pc^.adr:=nil;
viz[1]:=1;
while pc<>nil do
begin
  q:=lista[pc^.nr];
  while q<>nil do
    begin
      cc:=lung[pc^.nr]+q^.cost;
      if cc<lung[q^.nr] then lung[q^.nr]:=cc;
      if viz[q^.nr]=0 then begin
                             new(q1);
                             viz[q^.nr]:=1;
                             q1^.nr:=q^.nr;
                             q1^.adr:=nil;
                             uc^.adr:=q1;
                             uc:=q1;
                           end;
      q:=q^.adr;
    end;
  q1:=pc;
  {viz[pc^.nr]:=0;}
  pc:=pc^.adr;
  dispose(q1);
end;

close(f);
assign(f,'dijkstra.out');
rewrite(f);
for i:=2 to n do
  if lung[i]<2140000000 then write(f,lung[i],' ')
            else write(f,0,' ');
close(f);
end.