P3547 [POI 2013] CEN-Price List

铁路一直是 Byteotia 最受欢迎的交通方式。 在这个国家的 $n$ 个城镇中，有 $m$ 对城镇由 Byteotian State Railways (BSR) 的轨道段连接。 这些轨道不会在城镇外交叉，可能会经过风景如画的桥梁和不太风景如画的隧道。 直接通过铁路连接的任意两个城镇之间的票价为 $a$ 比特勒。 目前，Byteotia 的交通市场正在发生变化。 截至目前，BSR 面临着一个新的竞争对手：Byteotian Airlines (BA)。 BA 计划在一些城镇对之间运营航班。 由于 Byteotian 铁路相当舒适，BA 董事会决定只在那些没有直接铁路连接的城镇对之间运营航班。出于经济原因，BA 只会在那些需要恰好一次换乘的城镇之间飞行。 每张此类航班的票价为 $b$ 比特勒。 为了帮助 Byteotia 的市民规划他们的旅行，Byteotian 交通部 (BMT) 决定发行传单，说明所有可能城镇之间的最便宜路线。任意数量的直接铁路或飞机连接的序列被称为路线。名叫 Byteasar 的 BMT 官员被委派准备传单的价格表。 你能帮他写一个程序来确定正确的价格吗？ 让我们明确一下，Byteotia 的所有连接，无论是铁路还是飞机，都是双向的。

无

无

------------ 2024/2/4 添加了一部分来自 bzoj 的数据。 题面翻译由 ChatGPT-4o 提供。