SP10453 SPRING - Spring Loaded

Bob 刚从他的物理老师那里得到了一个新的玩具，名字叫超级螺旋弹簧加载绳（Super Coiled Spring Loaded String, 简称 SCSLS），它使用了一些螺旋弹簧，但里面没有磁铁。这个复杂的装置由 $N$ 根杆和 $M$ 个弹簧组成，每根弹簧连接两根不同的杆。所有弹簧沿着装置的纵向排列，而杆则垂直分布。杆的位置可以在纵向自由调整，但当两个相连的杆被拉开时，弹簧会产生一个恢复力。根据胡克定律，这个弹性力可以表示为 $|F| = kx$，这里 $k$ 是弹簧常数，$x$ 是弹簧的位移，$|F|$ 是力的绝对值。SCSLS 的特点是使用了零长度弹簧，每个弹簧都有自己的常数 $k_i$，这种弹簧在拉伸时其长度等于其位移。 Bob 想把这件新玩具固定在他的卧室墙上。他需要将这些杆水平放置，使得杆 $0$ 和杆 $N-1$ 之间的距离为 $D$ 单位，其余的杆位于这两者之间，可以任意排序。作为一个对玩具十分爱护的孩子，他希望找到一种弹簧上的最大力最小的配置，以延长弹簧的使用寿命。 例如，在图中的左侧，我们有 $N=4$ 根杆和 $M=4$ 个弹簧处于初始配置。假设弹簧常数分别是 $k_0 = 10, k_1 = 20, k_2 = 10, k_3 = 1$，而 Bob 希望两个端点杆之间的总距离为 $D=10$。在右侧的最佳配置中，各个弹簧所受的力分别是 $|F_0| = 40, |F_1| = 40, |F_2| = 40, |F_3| = 6$，这些力的最大值不超过 $40$。

每个测试用例由若干行组成。第一行包含三个整数 $N, M$ 和 $D$，分别表示杆的数量、弹簧的数量以及两端杆之间的距离（$2 \le N \le 1000, 1 \le M \le 1000, 1 \le D \le 10^5$）。接下来的 $M$ 行，每行包含两个整数 $a_i$ 和 $b_i$ 以及一个浮点数 $k_i$，表示第 $i$ 个弹簧连接杆 $a_i$ 和杆 $b_i$，弹簧常数为 $k_i$（$0 \le a_i, b_i < N, a_i \neq b_i, 0.1 \le k_i \le 100.0$）。

对于每个测试用例，输出一行，表示实现的有效配置下最大弹性力的最小可能值。结果应保留两位小数。 **本翻译由 AI 自动生成**