Program Dijkstra;
 const inf = 1234567;
 type vecini = ^vecin;
      vecin = record num:word; dist:integer; next:vecini; end;
 var f,g:text; a:array[1..50000,1..2]of vecini;
     heap:array[1..50000]of longint;
     b:array[1..50000]of word;
     c:array[1..50000]of word;
     n,nh:word; m:longint;
 procedure initiere;
  var x:longint; y,z:word; w:integer;
  begin
   assign (f,'dijkstra.in'); reset (f);
   assign (g,'dijkstra.out'); rewrite (g);
   readln (f,n,m);
   for x:=1 to n do begin
     new (a[x,1]);
     a[x,2]:=a[x,1];
   end;
   for x:=1 to m do begin
     readln (f,y,z,w);
     a[y,2]^.num:=z;
     a[y,2]^.dist:=w;
     new (a[y,2]^.next);
     a[y,2]:=a[y,2]^.next;
   end;
  end;
 procedure init_heap;
  var x:longint;
  begin
   nh:=n;
   for x:=2 to nh do begin
     heap[x]:=inf;
     b[x]:=x;
     c[x]:=x;
   end;
   b[1]:=1; c[1]:=1;
  end;
 procedure swap (x,y:longint);
  var z:longint;
  begin
   z:=heap[x]; heap[x]:=heap[y]; heap[y]:=z;
   z:=b[c[x]]; b[c[x]]:=b[c[y]]; b[c[y]]:=z;
   z:=c[x]; c[x]:=c[y]; c[y]:=z;
  end;
 procedure coboara (x:longint);
  var y:longint;
  begin
   if 2*x<=nh then begin
     y:=x;
     if heap[x]>heap[2*x] then y:=2*x;
     if 2*x+1<=nh then if heap[y]>heap[2*x+1] then y:=2*x+1;
     if x<>y then begin
       swap (x,y);
       coboara (y);
     end;
   end;
  end;
 procedure urca (x:longint);
  begin
   if x>1 then
     if heap[x div 2]>heap[x] then begin
       swap (x,x div 2);
       urca (x div 2);
     end;
  end;
 procedure alg_dijkstra;
  var x,y,z:longint;
  begin
   while (nh>0) and (heap[1]<>inf) do begin
     x:=c[1];
     a[x,2]:=a[x,1];
     while a[x,2]^.next<>nil do begin
       y:=a[x,2]^.num;
       if c[y]<=nh then begin
         z:=heap[1]+a[x,2]^.dist;
         if heap[b[y]]>z then begin
           heap[b[y]]:=z;
           urca (b[y]);
         end;
       end;
       a[x,2]:=a[x,2]^.next;
     end;
     swap (1,nh);
     dec (nh);
     coboara (1);
   end;
  end;
 procedure scrie;
  var x:longint;
  begin
   for x:=2 to n do
     if heap[b[x]]<>inf then write (g,heap[b[x]],' ') else write (g,'0 ');;
   writeln (g);
  end;
 begin
  initiere;
  init_heap;
  alg_dijkstra;
  scrie;
  close (f); close (g);
 end.