Минимальный остов (каркас, остовное дерево)

program spantree;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
const maxN=300;
var f,f1                    :text;
    d,from                  :array[1..maxN] of integer;
    mark                    :array[1..maxN] of boolean;
    a                       :array[1..maxN,1..maxN] of integer;
    n,m,i,u,v,s,k,min,r     :integer;
 
 
begin
 reset(f,'spantree.in');
 rewrite(f1,'spantree.out');
 read(f,n,m);
 for i:=1 to n do
  for v:=1 to n do a[i,v]:=-1;{заполнение матрицы смежности}
 
 for i:=1 to m do begin
   read(f,u,v,s);
   a[u,v]:=s;
   a[v,u]:=s;
 end;{считана матрица}
 close(f);
 
 for i:=2 to n do d[i]:=high(integer);
 
 while k<n do begin
 
  min:=high(integer);
  for i:=1 to n do
   if (d[i]<=min) and (not mark[i]) then begin min:=d[i]; v:=i end;
   {нахождение минимального ребра из не U в U}
   if v<>1 then r:=r+a[from[v],v];{добавление ребра в ответ и в множество U}
   if d[v]=high(integer) then begin write(f1,'-1'); close(f1); halt end;
   mark[v]:=true;{помечаем v} inc(k);
   for i:=1 to n do
    if (not mark[i]) and (a[v,i]>-1) and (a[v,i]<d[i]) then begin
     d[i]:=a[v,i];
     from[i]:=v
    end;{пробегаем соседей v и изменяем кратчайший путь до них из U}
 
 end;
  write(f1,r);
  close(f1);
end.

const maxN=300;
var f,f1                    :text;
    d,from                  :array[1..maxN] of int64;
    mark                    :array[1..maxN] of boolean;
    a                       :array[1..maxN,1..maxN] of int64;
    n,m,s,k,min,r,i,u,v     :integer;
 
 
begin
 reset(f,'spantree.in');
 rewrite(f1,'spantree.out');
 read(f,n,m);
 for i:=1 to n do
  for v:=1 to n do a[i,v]:=-1;{заполнение матрицы смежности}
 
 for i:=1 to m do begin
   read(f,u,v,s);
   a[u,v]:=s;
   a[v,u]:=s;
 end;{считана матрица}
 close(f);
 
 for i:=2 to n do d[i]:=high(integer);
 
 while k<n do begin
 
  min:=high(integer);
  for i:=1 to n do
   if (d[i]<=min) and (not mark[i]) then begin min:=d[i]; v:=i end;
   {нахождение минимального ребра из не U в U}
   if d[v]=high(integer) then begin write(f1,'-1'); close(f1); halt end;
   {если выбрана вершина с бесконечным путём, то граф не связен}
   if (v>1) and (from[v]>0) then r:=r+a[from[v],v];{добавление ребра в ответ и в множество U}
   mark[v]:=true;{помечаем v} inc(k);
   for i:=1 to n do
    if (not mark[i]) and (a[v,i]>-1) and (a[v,i]<d[i]) then begin
     d[i]:=a[v,i];
     from[i]:=v
    end;{пробегаем соседей v и изменяем кратчайший путь до них из U}
 
 end;
  write(f1,r);
  close(f1);
end.