type rec=record
             x,y,c:longint;
         end;

var e:array[1..50001] of rec;
    c:array[1..50001] of longint;
    n,m,i,j,x,y:longint;
    ok:boolean;
begin
assign(input,'dijkstra.in'); reset(input);
assign(output,'dijkstra.out'); rewrite(output);
readln(n,m);
for i:=1 to m do readln(e[i].x,e[i].y,e[i].c);
for i:=1 to n do c[i]:=1000000001;
c[1]:=0;
i:=1;
ok:=true;
while (ok)and(i<n) do
   begin
     ok:=false;
     for j:=1 to m do
        begin
          x:=e[j].x; y:=e[j].y;
          if (c[y]>c[x]+e[j].c) then
              begin
                 c[y]:=c[x]+e[j].c;
                 ok:=true;
              end;
        end;
   inc(i);
   end;
for i:=2 to n do
   if c[i]=1000000001 then write('0 ') else write(c[i],' ');
close(input); close(output);
end.