11269: 【原1269】最小差异值2

题目

题目描述

author: 黄宇扬 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1269

Description

前情提要：http://acm.sjtu.edu.cn/OnlineJudge/problem/1266

不久后，P省又发生了地震，因为省长治理有方，现在P省的规模变大了很多。

省长仍然希望最贵道路的价格和最便宜道路的价格的差值尽量小，请你尽快地安排一种合理的方案，满足省长的要求。

Input Format

输入共有两行。

第一行两个数N，M，表示城市的个数以及可以修的公路数；

第二行开始M行，每行三个数a,b,c，表示a,b之间可以修一条价值c的无向道路（可能有自环）。

70%数据满足N<=M<=5000

100%数据满足N<=M<=100000，0<c<=100000;

Output Format

一个数表示该方案中最大边减去最小边的值，要求要尽量的小。

Sample Input

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

Sample Output

1686

(选第4，5，6，9条边即可。)

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！