const inf=250000001;
type muchie=^pmuchie;
     pmuchie= record
                x,y:word;
                c:integer;
                leg:muchie;
                end;
var prim:muchie;
    d:array[1..50001] of longint;
    n:word;
    m:longint;

procedure citeste;
var i:longint;
    p:muchie;
begin
assign(input,'dijkstra.in');reset(input);
readln(n,m);
for i:=1 to m do
begin
new(p);readln(p^.x,p^.y,p^.c);
p^.leg:=prim;prim:=p;
end;
close(input);
end;

procedure bellman;
var ok:Boolean;
    i:word;
    p:muchie;
begin
for i:=1 to n do
d[i]:=inf;
d[1]:=0;
 ok:=true;
while ok do
  begin
  ok:=false; p:=prim;
  while p<>nil do
    begin
    if d[p^.y]>d[p^.x]+p^.c then
            begin
            d[p^.y]:=d[p^.x]+p^.c;
            ok:=true;
            end;
    p:=p^.leg;
    end;
  end;
end;

procedure afisare;
var i:word;
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
citeste;
bellman;
afisare;
end.