const inf=maxint;
var a:array[1..50000,1..50000] of longint;
    d,use:array[1..250000] of longint;
    i,j,k,poz,n,m,c,min:longint;
    f,g:text ;
procedure citire;
begin
assign(f,'dijkstra.in');reset(f);
assign(g,'dijkstra.out');rewrite(g);
read(f,n,m);
for i:=1 to n do
 for j:=1 to n do a[i,j]:=inf;
for i:=1 to n do a[i,i]:=0;
for i:=1 to m do
    begin
    read(f,k,j,c);
    a[k,j]:=c;
    end;
close(f);
end;

procedure dijkstra;
begin
use[1]:=1;
for i:=2 to n do
 d[i]:=a[1,i];
for i:=1 to n do
  begin
  min:=inf;
  for j:=2 to n do
   if use[j]=0 then
     if d[j]<min then begin
                      min:=d[j];
                      poz:=j;
                      end;
  use[poz]:=1;
  for j:=2 to n do
  if use[j]=0 then
    if d[j]>d[poz]+a[poz,j] then
       begin
       d[j]:=d[poz]+a[poz,j];
       end;
   end;
end;

begin
citire;


use[1]:=1;
for i:=2 to n do
 d[i]:=a[1,i];
for i:=1 to n do
  begin
  min:=inf;
  for j:=2 to n do
   if use[j]=0 then
     if d[j]<min then begin
                      min:=d[j];
                      poz:=j;
                      end;
  use[poz]:=1;
  for j:=2 to n do
  if use[j]=0 then
    if d[j]>d[poz]+a[poz,j] then
       begin
       d[j]:=d[poz]+a[poz,j];
       end;
   end;
for i:=2 to n do
 write(g,d[i],' ');
close(g);
end.