type muchie= record
      x,y:longint;
      cost:integer;
      end;
const nmax=50000;
const inf=100000000;
var f,g:text;
v:array[1..5*nmax] of muchie;
d:array[1..nmax]of longint;
nc,x,y,i,m,n,z:longint;
ok:boolean;
begin
assign(f,'dijkstra.in');
reset(f);
assign(g,'dijkstra.out');
rewrite(g);
readln(f,n,m);
for i:=1 to m do
   begin
     readln(f,x,y,z);
     v[i].x:=x;
     v[i].y:=y;
     v[i].cost:=z;
     if x=1 then d[y]:=z;
   end;
for i:=2 to n do
   if d[i]=0 then d[i]:=inf;
repeat
ok:=true;
   for i:=1 to m do
          if d[v[i].y]>d[v[i].x]+v[i].cost then
              begin
                d[v[i].y]:=d[v[i].x]+v[i].cost;
                ok:=false;
              end;
until ok;
for i:=2 to n do
  if d[i]= inf then write(g,'0 ')
     else write(g,d[i],' ');
close(g);
end.