program bell_man_ford;
const fi='dijkstra.in';
      fo='dijkstra.out';
type li=record
   nod,val:longint;
    end;
var f,g:text;
    v:array of array of li;
    bufin,bufout:array[1..65000] of char;
    n,m,a,b,c1,i,st,sf,nd:longint;
    c,cd,viz,s:array[1..100000] of longint;
begin

assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
settextbuf(f,bufin);
settextbuf(f,bufout);
read(f,n,m);
setlength(v,n+1,1);

for i:=1 to m do
   begin
   read(f,a,b,c1);
   inc(c[a]);
   setlength(v[a],c[a]+1);
   v[a,c[a]].nod:=b;
   v[a,c[a]].val:=c1;
   end;
st:=0;
sf:=1;
for i:=2 to n do
   s[i]:=maxlongint;
s[1]:=0;
cd[1]:=1;
viz[1]:=1;
while st<sf do
   begin
   inc(st);
   nd:=cd[st];
   viz[nd]:=0;
   for i:=1 to c[nd] do
      begin
            if s[nd]+v[nd,i].val<s[v[nd,i].nod] then
         begin
        s[v[nd,i].nod]:=s[nd]+v[nd,i].val;
        if viz[v[nd,i].nod]=0 then
           begin
           inc(sf);
           cd[sf]:=v[nd,i].nod;
           viz[v[nd,i].nod]:=1;
           end;
        end;
      end;

   end;
for i:=2 to n do
    if s[i]=maxlongint then
       write(g,0,' ')
       else
       write(g,s[i],' ');
close(f);
close(g);
end.