题目描述 Description
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。*派人修复这些公路。
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
输入描述 Input Description
第1行两个正整数N，M（N<=1000，M<=100000）
下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。（x<=N，y<=N，t<=100000）
输出描述 Output Description
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。
样例输入 Sample Input
4 4
1 2 6
1 3 4
1 4 5
4 2 3
样例输出 Sample Output
5
/*
题目的意思很容易就得出：这个题是求一张图的最小生成树的最大边的。
写程序的时候，没注意把father[x1]=y1;写成了father[x1]==y1;结果只有20分啊！
*/
#define N 1005
#define M 100010
#include<iostream>
using namespace std;
#include<cstdio>
#include<algorithm>
int n,m;
struct Edge{
int u,v,w;
bool operator <(Edge P)
const{return w<P.w;}
}edge[M];
int father[N];
void input()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
sort(edge+,edge+m+);
}
int find1(int x)
{
return (father[x]==x)?x:father[x]=find1(father[x]);
}
int kruskal()
{
for(int i=;i<=n;++i)
father[i]=i;
int sum=;
for(int i=;i<=m;++i)
{
int x1=find1(edge[i].u);
int y1=find1(edge[i].v);
if(x1!=y1)
{
sum++;
father[x1]=y1;
if(sum==n-)
return edge[i].w;
}
}
return -;
}
int main()
{
input();
printf("%d\n",kruskal());
return ;
}