SP10087 SENSORNT - Sensor Network

为了满足 SWERC 2010 出题团队的要求，我们在总部安装了一套传感器网络。出题团队对题目机密信息泄露的恐惧促使他们做出了这个决定。 然而，在仓促之间，他们忽略了需要搭建电力网络来让传感器正常工作。结果，安全系统还未投入使用，但为了不让大量的资源投入浪费，安装必须在比赛结束之前完成。因此，你需要编写一个程序帮助电工完成任务。 出题团队不惜代价，从一家知名公司购置了传感器。每个传感器都是手工制作，并且标有一个推荐的工作电压。虽然可以在比推荐值更高的电压下运行，但这样会增加故障的风险，电压绝不能低于推荐值。当电工看到这些传感器时，他对几乎每个传感器都有不同的推荐电压感到惊讶！这些传感器被安装得恰好控制两扇门，并且每扇门都至少由一个传感器控制。现在是为传感器供电的时候了，电工面临以下限制： - 幸运的是，不需要激活所有传感器。我们要求选定的传感器子集能确保每扇门至少由子集中的一个传感器控制。 - 电力将先提供给一个激活的传感器，然后通过电线传递给其他传感器。为了节约电线，连接只能发生在相邻的激活传感器之间（“相邻”是指共同控制一扇门的传感器）。由于必须向每个激活的传感器供电，因此并非所有传感器子集都能适合作为选定的工作传感器子集。 - 因为所有传感器会被供应相同的电压，所以电压值不能低于任何一个传感器的推荐电压。 为简化讨论，我们称同时满足上述两个限制条件的传感器子集为可接受子集。网络设计使得所有传感器的集合总是可接受的，但我们希望选择更小的子集以尽可能减小“电压差”，定义为该子集中任意两个传感器上的电压之差的绝对值最大者。这样可以最大限度地降低故障风险。 电工没有能解决找出具有最小电压差的可接受子集的问题。因此，电力安装仍未完成。今天，我们邀请你编写一个程序，分析给定的传感器网络和每个传感器的推荐电压，找出答案。

输入由多个测试用例组成，每个测试用例之间有一个空行分隔。每个测试用例开始于一行整数 $n$ (2 ≤ n ≤ 10^5)，表示传感器数量。接下来是 $m$ 行描述传感器的信息，每行包含三个整数 $a$ (0 ≤ a < n), $b$ (0 ≤ b < n) 和 $w$ (1 ≤ w ≤ 10^9)，表示第 $i$ 个传感器控制的两扇门编号为 $a$ 和 $b$，同时 $w$ 是其推荐电压。可确保没有两个传感器控制相同的一对门。 输入以单独一个数字 0 的一行结束。

对于每个测试用例，输出一行，显示可接受子集的最小电压差。

- $2 \leq n \leq 10^5$ - $n - 1 \leq m \leq \frac{n(n-1)}{2}$ - $0 \leq a, b < n$ - $1 \leq w \leq 10^9$ **本翻译由 AI 自动生成**