In order to prepare the “The First National ACM School Contest” (in 20??) the major of the city
decided to provide all the schools with a reliable source of power. (The major is really afraid of
blackoutsJ). So, in order to do that, power station “Future” and one school (doesn’t matter which one)
must be connected; in addition, some schools must be connected as well.
You may assume that a school has a reliable source of power if it’s connected directly to “Future”,
or to any other school that has a reliable source of power. You are given the cost of connection between
some schools. The major has decided to pick out two the cheapest connection plans – the cost of the
connection is equal to the sum of the connections between the schools. Your task is to help the major
— find the cost of the two cheapest connection plans.
Input
The Input starts with the number of test cases, T (1 < T < 15) on a line. Then T test cases follow. The
first line of every test case contains two numbers, which are separated by a space, N (3 < N < 100)
the number of schools in the city, and M the number of possible connections among them. Next M
lines contain three numbers Ai
, Bi
, Ci
, where Ci
is the cost of the connection (1 < Ci < 300) between
schools Ai and Bi
. The schools are numbered with integers in the range 1 to N.
Output
For every test case print only one line of output. This line should contain two numbers separated by a
single space – the cost of two the cheapest connection plans. Let S1 be the cheapest cost and S2 the
next cheapest cost. It’s important, that S1 = S2 if and only if there are two cheapest plans, otherwise
S1 < S2. You can assume that it is always possible to find the costs S1 and S2.
Sample Input
2
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10
Sample Output
110 121
37 37
题意：
找最小生成树，和次最小生成树，
用kruskal算法，先求出最小数，并把每个路径标记，
然后再用相同的方法求次短路，具体就是：每次去掉一个标记过的边，然后遍历完，找到这个时候的最短路，一共去掉n-1条边，依次遍历找到当时的最短路，最后再在其中找最小的那个，就是次短路了

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=888;
int MAX=0x3f3f3f3f;
int n,m;
int dist[N],map[N][N];
int biao[N];
int sum[N];
int x[N],y[N];
int mm[N];
int pre[N];
struct node{
	int u,v,w;
}a[N*(N-1)/2];
bool cmp(node a,node b)
{
	return a.w<b.w;
}
int find(int x)
{
	if(pre[x]==x)
	return x;
	else
	return pre[x]=find(pre[x]);
}
int judge(int u,int v)
{
	int fx=find(u);
	int fy=find(v);
	if(fx!=fy)
	{
		pre[fx]=fy;
		return 1;
	}
	return 0;
}
void unit()
{
	for(int i=1;i<=n;i++)
	{
		pre[i]=i;
	}
}
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
   	cin>>n>>m;
   	unit();//每个点的根节点是自己
   	memset(biao,0,sizeof(biao));
   	for(int i=0;i<m;i++)
   	{
   	  cin>>a[i].u>>a[i].v>>a[i].w;
	}
	sort(a,a+m,cmp);
	int ans=0,num=0;
	for(int i=0;i<m;i++)
	{
		if(judge(a[i].u,a[i].v))
		{
			ans+=a[i].w;
			num++;
			biao[i]=1;
			if(num==n-1)
			break;
		}
	}
	int minn=ans;
	int minnn=MAX;
	for(int i=0;i<m;i++)
	{
		ans=0,num=0;
		if(biao[i]==1)//去掉一条标记过的边
		{
			unit();//重新初始化
			for(int j=0;j<m;j++)
			{
				if(i==j)
				continue;
		    if(judge(a[j].u,a[j].v))
	    	{
			ans+=a[j].w;
			num++;
			
			if(num==n-1)
			{
				minnn=min(minnn,ans);
					break;
			}
		
	    	}
			}
		}
	}
	   cout<<minn<<" "<<minnn<<endl;
   }
    return 0;
}