const nmax=50000;
      lmax=1000;
      faradrum=(nmax-1)*lmax+1;
      mmax=250000;
type muchie=record
            x,y:word;
            c:1..lmax;
            end;
var n,i:word;
    m:longint;
    drum:array[1..nmax]of longint;
    ok:boolean;
    g:array[1..mmax]of muchie;

begin
assign(input,'dijkstra.in');
reset(input);
assign(output,'dijkstra.out');
rewrite(output);
readln(n,m);
for i:=1 to m do with g[i] do readln(x,y,c);
drum[1]:=0;
for i:=2 to n do drum[i]:=faradrum;
repeat
ok:=false;
for i:=1 to m do if drum[g[i].y]>drum[g[i].x]+g[i].c then
  begin
  drum[g[i].y]:=drum[g[i].x]+g[i].c;
  ok:=true;
  end;
until ok;
for i:=2 to n do if drum[i]=faradrum then write('0 ')
                                     else write(drum[i],' ');
close(input);
close(output);
end.