```pascal
var n,m,i,root1,root2,ans:longint; fa,x,y,z:array[0..100005] of longint;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;
a:=b;
b:=t;
end;
procedure sort(l,r:longint);
var
i,j,mid:longint;
begin
i:=l;
j:=r;
mid:=z[random(r-l+1)+l];
while i<j do
begin
while z[i]<mid do inc(i);
while mid<z[j] do dec(j);
if not(i>j) then
begin
swap(z[i],z[j]);
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i);
j:=j-1;
end;
end;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
function getfather(x:longint):longint;
begin
if x<>fa[x] then fa[x]:=getfather(fa[x]);
exit(fa[x]);
end;
procedure join(x,y:longint);
begin
fa[y]:=x;
end;
begin
readln(n,m);
for i:=1 to m do
readln(x[i],y[i],z[i]);
for i:=1 to n do
fa[i]:=i;
sort(1,m);
for i:=1 to m do
begin
root1:=getfather(x[i]);
root2:=getfather(y[i]);
if root1<>root2 then
begin
join(root1,root2);
ans:=ans+z[i];
end;
end;
write(ans);
end.
```
by yqh123 @ 2018-07-03 20:44:37
已AC，数组没开大
by yqh123 @ 2018-07-03 20:51:25