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]:=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);
  begin
   if ph[x]>1 then
     if dist[x]<dist[heap[ph[x] div 2]] then begin
       swap (ph[x],ph[x] div 2);
       upheap (x);
     end;
  end;
 procedure downheap (x:word);
  var y:word;
  begin
   if 2*ph[x]<=nh then begin
     y:=x;
     if dist[x]>dist[heap[2*ph[x]]] then y:=heap[2*ph[x]];
     if 2*ph[x]+1<=nh then if dist[y]>dist[heap[2*ph[x]+1]] then y:=heap[2*ph[x]+1];
     if x<>y then begin
       swap (ph[x],ph[y]);
       downheap (x);
     end;
   end;
  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 (heap[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 (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,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.