UOJ Logo

NOI.AC

#73. 道路重建

统计

【问题描述】

8012年因为外星人的攻击波及到了地球上部分城市,导致波及到了试验舱所统领下的JS省n个城市之间的道路都损坏掉了,SR希望聪明的你们能将城市之间的道路重修一遍。 很多城市之间的地基都被地震破坏导致不能修路了,因此可供修建的道路只有 m 条。因为施工队伍有限,SR要求用尽量少的道路将所有的城市连通起来(两两城市之间至少有一条有道路形成的路径连通),这样施工量就可以尽量少。不过,省长为了表示自己的公正无私,要求在满足上述条件的情况下,选择一种方案,使得该方案中最贵道路的价格和最便宜道路的价格的差值尽量小,即使这样的方案会使总价提升很多也没关系。 求最小可能的差值。

【输入格式】

第一行包含两个整数 n,m。 接下来 m 行,每行包含三个整数 $a$,$b$ ,$c$,表示城市 $a$,$b$ 之间可以修建一条价格为 $c$ 的无向道路。

【输出格式】

若存在合法方案,则第一行包含一个整数,表示最贵道路的价格和最便宜道路的价格的最小差值; 否则第一行包含一个整数 −1。

【输入样例】

5 10
1 2 9384
1 3 887
1 4 2778
1 5 6916
2 3 7794
2 4 8336
2 5 5387
3 4 493
3 5 6650
4 5 1422

【输出样例】

1686

【数据规模】

对于 30% 的数据, n,m ≤ 20。

对于 60% 的数据, n ≤ 1000, m ≤ 4000。

对于 100% 的数据, 2 ≤ n ≤ 2000, 0 ≤ m ≤ 15000, a b, 1 ≤ c ≤ 2 × $10^9$。