Pagini recente » Monitorul de evaluare | Cod sursa (job #1631564)
program apm;
type el=record
x,y,c:longint;
end;
var bufin,bufout:array[1..1 shl 17] of char;
f,g:text;
n,m,s,k,i:longint;
t,nr:array[1..200005] of longint;
v:array[1..400005] of el;
function tata(nod:longint):longint;
begin
if t[nod]<0 then
tata:=nod
else
begin
t[nod]:=tata(t[nod]);
tata:=t[nod];
end;
end;
function pivot(st,dr:longint):longint;
var di,dj,i,j,auxx:longint;
aux:el;
begin
i:=st;
j:=dr;
di:=0;
dj:=1;
while i<j do
begin
if v[i].c>v[j].c then
begin
aux:=v[i];
v[i]:=v[j];
v[j]:=aux;
auxx:=di;
di:=dj;
dj:=auxx;
end;
i:=i+di;
j:=j-dj;
end;
pivot:=i;
end;
procedure quicksort(st,dr:longint);
var p:longint;
begin
if st<dr then
begin
p:=pivot(st,dr);
quicksort(st,p-1);
quicksort(p+1,dr);
end;
end;
procedure apm;
var i,a,b:longint;
begin
k:=0;
for i:=1 to n do
t[i]:=-1;
for i:=1 to m do
begin
a:=tata(v[i].x);
b:=tata(v[i].y);
if a<>b then
begin
t[b]:=a;
k:=k+1;
nr[k]:=i;
s:=s+v[i].c;
end;
end;
end;
procedure afisare;
var j:integer;
begin
writeln(g,s);
writeln(g,n-1);
for j:=1 to k do
writeln(g,v[nr[j]].x,' ',v[nr[j]].y);
close(f);
close(g);
end;
begin
assign(f,'apm.in');
assign(g,'apm.out');
settextbuf(f,bufin);
settextbuf(g,bufout);
reset(f);
rewrite(g);
readln(f,n,m);
for i:=1 to m do
begin
readln(f,v[i].x,v[i].y,v[i].c);
end;
quicksort(1,m);
apm;
afisare;
end.