Program dijkstr;
var fi,fo :text;
    i,n,m : longint;
    a,b,c,d : array[0..250000] of longint;  t:boolean;
begin
    assign(fi,'dijkstra.in'); reset(fi); readln(fi,n,m);
    assign(fo,'dijkstra.out'); rewrite(fo);      t:=true;
    for i:=1 to m do readln(fi,a[i],b[i],c[i]);
    for i:=1 to n do d[i]:=-1; d[1]:=0;

while t=true do begin
   t:=false;
   for i:=1 to m do
       if (d[a[i]]<>-1) and ((d[a[i]]+c[i]<d[b[i]]) or (d[b[i]]=-1)) then
                                      begin
                                      d[b[i]]:=d[a[i]]+c[i];
                                      t:=true;
                                      end;

end;

    for i:=2 to n do
           if d[i]>=0 then write(fo,d[i],' ')
                      else write(fo,'0',' ');
    close(fi); close(fo);
end.