Program dijkstra;
 var f,g:text; a:array[1..33000,1..33000]of 0..1000;
     b:array[1..50000]of boolean;
     c:array[1..50000]of longint;
     n,m:longint;
 procedure initiere;
  var x,y,z:longint;
  begin
   assign (f,'dijkstra.in'); reset (f);
   assign (g,'dijkstra.out'); rewrite (g);
   readln (f,n,m);
   for x:=1 to m do read (f,y,z,a[y,z]);
  end;
 procedure incheiere;
  var x:longint;
  begin
   for x:=1 to n do if c[x]<>maxlongint then write (g,c[x],' ') else write (g,0,' ');
   close (f); close (g);
  end;
 function minim (x,y:longint):longint;
  begin
   if x<y then exit (x) else exit (y);
  end;
 procedure calcul;
  var x,y,u,v:longint; p:boolean;
  begin
   for x:=1 to n do begin
     b[x]:=false;
     c[x]:=maxlongint;
   end;
   x:=1;
   b[1]:=true;
   c[1]:=0;
   p:=true;
   while p do begin
     p:=false;
     v:=maxlongint;
     for y:=1 to n do
       if (a[x,y]<>0) and not b[y] then begin
         p:=true;
         c[y]:=minim (c[y],c[x]+a[x,y]);
         if c[y]<v then begin
           u:=y;
           v:=c[y];
         end;
       end;
     b[x]:=true;
     x:=u;
   end;
  end;
 begin
  initiere;
  calcul;
  incheiere;
 end.