<center style="color&#58;rgb&#40;51&#44;51&#44;51&#41;&#59;font&#45;family&#58;&#39;Helvetica Neue&#39;&#44; Helvetica&#44; Arial&#44; sans&#45;serif&#59;font&#45;size&#58;14px&#59;">

Problem A: 灾区重建

Time Limit: 3 Sec   Memory Limit: 128 MB
Submit: 123   Solved: 32
[ Submit][ Status][ Web Board] </center>

Description

    在一场地震之后，原本美丽的C国变成了一片废墟，但是这并没有击垮人们的意志，在各方的支持下救援队马上开始了灾区重建。已知C国一共由N个城市（编号从1~N）组成，在这N个城市之间有M条道路连通着各个城市，现在要将物资运往各个城市，但是每条道路都有其最大承重量W，也就是说如果一辆车所运载的货物重量大于W的话是无法通过这条路的。为了防止道路崩塌同时提高效率，我们都会去走承重量尽可能大的道路，现在救援队的队长想知道如果要将货物从任意一个城市运往其他N-1个城市，一次所能运输的最大重量是多少，你能告诉他吗？

Input

输入第一行为一个整数T(T<=10），表示有T组样例；

第二行为两个整数N(N<=10^5)和M(M<=10^6)，分别表示城市的数量和道路的数量；

接下来M行每行有三个整数,u,v,w，（u,v<=N，w<=10^9）

表示u和v之间有一条承重量为w的道路（道路是双向的，即可以从u走到v，也可以从v走到u，同时数据保证任意两个城市之间至多只会有一条道路）。


Output

每组样例输出一行

Case #X: Y，X表示第几组样例，Y便是所要求的答案。

Sample Input

1
4 6
1 2 2
1 3 1
1 4 9
2 4 8
2 3 10
3 4 4

Sample Output

Case #1: 8

HINT


样例解释：



如果要将物资从1运输到2，那么走1-4-2这条路径所即能运输的最大重量为8；



如果要将物资从1运输到3，那么走1-4-2-3这条路径即所能运输的最大重量为8；



如果要将物资从1运输到4，那么走1-4这条路径即所能运输的最大重量为9； 



如果要将物资从2运输到3，那么走2-3这条路径即所能运输的最大重量为10； 



如果要将物资从2运输到4，那么走2-4这条路径即所能运输的最大重量为8； 



如果要将物资从3运输到4，那么走3-2-4这条路径即所能运输的最大重量为8； 



故答案为8。


很裸的一道最大生成树，求最大生成树的最大权边，注意跳出就不会超时。

#include<stdio.h>
#include<string.h>
#include<algorithm>
int t,n,m,i,j;
using namespace std;
 
struct s{
     int a,b,c;
}k[1000005];
 
const int maxn=1000005;
 
bool bmp(s a, s b)
{
     return a.c>b.c;
}
 
int par[maxn];
void init()
{
     for ( int i=0;i<=n;i++){
         par[i]=i;
     }
}
int find( int x)
{
     if (par[x]==x) return x;
     else {
         return par[x]=find(par[x]);
     }
}
void unite( int x, int y)
{
     x=find(x);
     y=find(y);
     if (x==y) return ;
     else {
         par[y]=x;
     }
}
 
int main()
{
     scanf ( "%d" ,&t);
     for (i=0;i<t;i++)
     {
         scanf ( "%d%d" ,&n,&m);
         init();
         for (j=0;j<m;j++)
             scanf ( "%d%d%d" ,&k[j].a,&k[j].b,&k[j].c);
         sort(k,k+m,bmp);
         int res=0,l=0;
         for (j=0;j<m;j++)
         {
             if (find(k[j].a)!=find(k[j].b))
             {
                 unite(k[j].a,k[j].b);
                 res=k[j].c;
                 if (++l==n-1) break ;
             }
             if (l==n-1) break ;
         }
         printf ( "Case #%d: %d\n" ,i+1,res);
     }
     return 0;
}