NKRACING - Vòng đua F1
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
maxn=10010;
maxm=100010;
var re,n,m:longint;
b:array[0..maxm,0..2] of longint;
cha,sl:array[1..maxn] of longint;
procedure rf;
var i,j:longint;
begin
read(n,m);
for i:=1 to m do
for j:=0 to 2 do
read(b[i,j]);
for i:=1 to n do
begin
cha[i]:=i; sl[i]:=1;
end;
end;
procedure sort(l,r:longint);
var i,j,x:longint;
begin
i:=l; j:=r; x:=b[(i+j) shr 1,2];
repeat
while b[i,2]>x do i:=i+1;
while b[j,2]<x do j:=j-1;
if i<=j then
begin
b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function find(x:longint):longint;
begin
if cha[x]=x then find:=x
else
begin
cha[x]:=find(cha[x]);
find:=cha[x];
end;
end;
procedure pr;
var i,j,x,y,xx,yy,dem:longint;
begin
sort(1,m);
for i:=1 to m do
begin
x:=b[i,0]; y:=b[i,1];
xx:=find(x); yy:=find(y);
if xx=yy then re:=re+b[i,2]
else
begin
dem:=dem+1;
if sl[xx]>=sl[yy] then
begin
cha[yy]:=xx;
sl[xx]:=sl[xx]+sl[yy];
end
else
begin
cha[xx]:=yy;
sl[yy]:=sl[yy]+sl[xx];
end;
if dem=n-1 then break;
end;
end;
for j:=i+1 to m do re:=re+b[j,2];
writeln(re);
end;
begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.