题目描述

A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。 给出 A 地区的村庄数 N，和公路数 M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

输入格式

第 1 行两个正整数 N,M。 下面 M 行，每行 3 个正整数 x,y,t，告诉你这条公路连着 x,y 两个村庄，在时间 t 时能修复完成这条公路。

输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 -1，否则输出最早什么时候任意两个村庄能够通车。

样例

输入样例 1

4 4
1 2 6
1 3 4
1 4 5
4 2 3

输出样例 1

5

输入样例 2

4 2
1 2 10
3 4 20

输出样例 2

-1

输入样例 3

2 1
1 2 100

输出样例 3

100

提示

数据规模：1≤x,y≤N≤10^3，1≤M,t≤10^5。

思路分析：可以将这N个村庄看成N个点，其中M是我们要合并的次数。 很明显，修路时间t越早的就要越早合并，所以要先排序！(时间短的排前面) 排序后，按照时间逐个合并，如果合并过程中道路连通，那么输出时间;否则输出-1 但是如果按时间排序，x,y也要跟着动，怎么办呢？用结构体把x,y,t打包！

我们设fa[i]是第i个人的祖先，初始化fa[i]=i，各自是各自的祖先 当合并一次之后，我们扫一遍fa数组，统计fa[i]=i的个数： 如果只有1个fa[i]=i，就说明所有的全部联通了（因为只有1个人是自己的祖先，别的人都跟着他） 如果不止1个，就说明当前没有全部联通（因为两个人互相没有关系），需要继续合并。