Program dijsktra;
 type list = ^cell;
      cell = record
                no:word;
                di:longint;
                ur:list;
              end;
 var f,g:text; a:array[1..50000,1..2]of list;
     dist:array[1..50000]of longint;
     heap:array[1..50000]of word;
     ph:array[1..50000]of word;
     n,nh:word; m,i:longint;
 procedure creaza_a;
  var x:longint; y:word;
  begin
   for x:=1 to m do begin
     readln (f,y,a[y,2]^.no,a[y,2]^.di);
     new (a[y,2]^.ur);
     a[y,2]^.ur^.ur:=nil;
     a[y,2]:=a[y,2]^.ur;
   end;
  end;
 procedure init_heap;
  var x:longint;
  begin
   for x:=2 to n do begin
     dist[x]:=maxlongint;
     heap[x]:=x;
     ph[x]:=x;
   end;
   nh:=n; dist[1]:=0; heap[1]:=1; ph[1]:=1;
  end;
 procedure swap (x,y:word);
  var z:word;
  begin
   z:=heap[x]; heap[x]:=heap[y]; heap[y]:=z;
   ph[heap[x]]:=x; ph[heap[y]]:=y;
  end;
 procedure upheap (x:word);
  var y:word;
  begin
   y:=x;
   while (y>1) and (dist[heap[y]]<dist[heap[y div 2]]) do begin
     swap (y,y div 2);
     y:=y div 2;
   end;
  end;
 procedure downheap (x:word);
  var y,z:word;
  begin
   y:=x;
   repeat
     z:=0;
     if 2*y<=nh then begin
       z:=2*y;
       if z+1<=nh then if dist[heap[z+1]]<dist[heap[z]] then inc (z);
       if dist[heap[y]]<=dist[heap[z]] then z:=0;
     end;
     if z<>0 then begin
       swap (y,z);
       y:=z;
     end;
   until z=0;
  end;
 procedure alg_dijkstra;
  var x,y:word;
  begin
   while nh>0 do begin
     x:=heap[1];
     if dist[x]=maxlongint then exit;
     swap (1,nh);
     dec (nh);
     downheap (1);
     a[x,2]:=a[x,1];
     while a[x,2]^.ur<>nil do begin
       y:=a[x,2]^.no;
       if ph[y]<=nh then
         if dist[x]+a[x,2]^.di<dist[y] then begin
           dist[y]:=dist[x]+a[x,2]^.di;
           upheap (ph[y]);
         end;
       a[x,2]:=a[x,2]^.ur;
     end;
   end;
  end;
 begin
  assign (f,'dijkstra.in'); reset (f);
  assign (g,'dijkstra.out'); rewrite (g);
  readln (f,n,m);
  for i:=1 to n do begin
    new (a[i,1]);
    a[i,1]^.ur:=nil;
    a[i,2]:=a[i,1];
  end;
  creaza_a;
  init_heap;
  alg_dijkstra;
  for i:=2 to n do if dist[i]<maxlongint then write (g,dist[i],' ') else write (g,'0 ');
  writeln (g);
  close (f); close (g);
 end.