Kruskal求图的次小生成树  
 算法：先求MST。分别删除MST中的每条边再求MST。在所有结果中取最小，即为次小生成树。 
以边目录方式输出，输出第一行为MST，第二行是次小生成树。 

const maxm=250000; 
      maxn=500; 
var bg,ed,l:array[1..maxm] of longint; 
    can:array[1..maxm] of boolean; 
    first,tfirst,fa:array[1..maxn+1] of longint; 
    n,m,ans1,ans2,i:longint; 
procedure QuickSort(left,right:longint); 
var i,j,mid,t:longint; 
begin 
     i:=left; j:=right; mid:=l[(left+right)shr 1]; 
     repeat 
           while(l[i]<mid)do inc(i); 
           while(l[j]>mid)do dec(j); 
           if(i<=j)then 
           begin 
                t:=bg[i]; bg[i]:=bg[j]; bg[j]:=t; 
                t:=ed[i]; ed[i]:=ed[j]; ed[j]:=t; 
                t:=l[i]; l[i]:=l[j]; l[j]:=t; 
                inc(i); dec(j); 
           end; 
     until i>j; 
     if i<right then QuickSort(i,right); 
     if left<j then QuickSort(left,j); 
end; 
function find(x:longint):longint; 
var tx,tx2,temp:longint; 
begin 
     tx:=x; 
     while fa[tx]<>tx do tx:=fa[tx]; 
     tx2:=x; 
     while fa[tx2]<>tx do 
     begin 
          temp:=fa[tx2];fa[tx2]:=tx;tx2:=temp; 
     end; 
     find:=tx; 
end; 
procedure kruskal; 
var i,t,tx,ty:longint; 
begin 
     for i:=1 to n do fa[i]:=i; 
     i:=0;t:=0; 
     repeat 
     inc(i); 
     if can[i] then 
     begin 
          tx:=find(bg[i]);ty:=find(ed[i]); 
          if tx<>ty then 
          begin 
               inc(t);fa[tx]:=ty; 
               inc(ans1,l[i]); 
               first[t]:=i; 
          end; 
     end; 
     until (t=n-1) or (i=m); 
     if (i=m) and (t<n-1) then ans1:=-1; 
end; 
begin 
     randomize; 
     readln(n,m); 
     for i:=1 to m do readln(bg[i],ed[i],l[i]); 
     QuickSort(1,m); 
     fillchar(can,sizeof(can),true); 
     kruskal; 
     writeln('Cost: ',ans1); 
     ans2:=maxlongint; 
     tfirst:=first; 
     for i:=1 to n-1 do 
     begin 
          can[tfirst[i]]:=false; 
          ans1:=0; 
          kruskal; 
          if(ans1>-1)and(ans1<ans2) then ans2:=ans1; 
          can[tfirst[i]]:=true; 
     end; 
     if ans2=maxlongint then ans2:=-1; 
     writeln('Cost: ',ans2); 
end.