题目描述

贝茜受雇在农夫约翰的(N)（(2 ≤ N ≤ 1000)）个谷仓之间搭建一个低成本的互联网网络，这些谷仓方便地编号为(1)到(N)。约翰已经做了一些勘测工作，发现了(M)（(1 ≤ M ≤ 20000)）条谷仓两两之间可能的连接路线。每条可能的连接路线都有一个相关的成本(C)（(1 ≤C ≤100000)）。约翰希望在连接网络上花费最少的钱，他甚至不想付给贝茜钱。

贝茜意识到约翰不会付钱给她，于是决定尽可能地把工作做得最差。她必须决定安装一组连接，以便（i）这些连接的总成本尽可能大；（ii）所有的谷仓都连接在一起（这样就可以通过已安装的连接路径从任何一个谷仓到达其他任何一个谷仓）；（iii）连接中没有环（约翰很容易就能检测到环）。条件（ii）和（iii）确保最终的连接集合看起来像一棵树。

输入

第(1)行：两个用空格分隔的整数：(N)和(M)

第(2)行到第(M + 1)行：每行包含三个用空格分隔的整数(A)、(B)和(C)，描述了谷仓(A)和谷仓(B)之间成本为(C)的连接路线。

输出

第(1)行：一个整数，表示连接所有谷仓的最昂贵的树的价格。如果不可能连接所有的谷仓，则输出(-1)。

5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17

42

提示

输出详情：

最昂贵的树的成本为(17 + 8 + 10 + 7 = 42)。它使用了以下连接：(4)到(5)，(2)到(5)，(2)到(3)，以及(1)到(3)。

来源

USACO 2004 年 12 月银牌赛