CF266D BerDonalds

著名的快餐连锁店 BerDonalds 计划在 Bertown 开设一家咖啡馆。选址的关键在于让顾客可以方便地抵达。Bertown 的道路系统由 $n$ 个路口和 $m$ 条双向道路组成。每条道路都有已知的长度。我们还知道，从任意一个路口出发，总可以经由道路到达其他任意一个路口。 你的任务是选择一个餐厅的位置，使得从咖啡馆出发到最远路口的最短距离最小。注意，餐厅不仅可以建在路口上，还可以建在任意一条道路的任意位置。

第一行包含两个整数 $n$ 和 $m$（$2\le n\le 200;n - 1 \le m \le \frac{n(n-1)}{2}$），分别表示路口数量和道路数量。接下来 $m$ 行，每行包含三个整数 $a_{i}, b_{i}, w_{i}$（$1 \leq a_{i}, b_{i} \leq n,\, a_{i} \neq b_{i};\, 1 \leq w_{i} \leq 10^{5}$），表示第 $i$ 条道路连接编号为 $a_i$ 和 $b_i$ 的路口，且长度为 $w_i$。 保证每条道路连接两两个不同的路口，任意两点之间最多只有一条道路，并且整个路网是连通的。

输出一个实数，表示从最优餐厅位置到最远路口的最小可能距离。若你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

由 ChatGPT 5 翻译