type muchie=record
            x,y,cost:longint;
            end;
const q=2000000000;
var v:array[1..250001]of muchie;
    d:array[1..50001]of longint;
    f,g:text;
    n,poz,pozz:word;
    m,i,s:longint;
    modif:boolean;
begin
assign(f,'dijkstra.in');reset(f);
assign(g,'dijkstra.out');rewrite(g);
read(f,n,m);
for i:=1 to m do begin
    read(f,poz,pozz,s);
    v[i].x:=poz;
    v[i].y:=pozz;
    v[i].cost:=s;
    if poz=1 then d[pozz]:=s;
end;

for i:=2 to n do if d[i]=0 then d[i]:=q;

repeat
modif:=false;
for i:=1 to m do begin
          s:=d[v[i].x]+v[i].cost;
          poz:=v[i].y;
          if s<d[poz] then begin
                           d[poz]:=s;
                           modif:=true;
                           end;
          end;
until not modif;
for i:=2 to n do if d[i]<>q then write(g,d[i],' ')
                                     else write(g,0,' ');
close(g);
end.