幸福国度可以用 个城镇（用 到 编号）构成的集合来描述，这些城镇最开始由 条双向道路（用 到 编号）连接。城镇 是中央城镇。保证一个人从城镇 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是收费道路，道路 的使用者必须向道路的主人支付 分钱的费用。已知所有的这些 是互不相等的。最近有 条新道路建成，这些道路都属于亿万富豪 Mr.Greedy。Mr.Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣布这些费用。
两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这些道路游行并前往中央城镇。共计 个参与者将从城镇 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就是 Mr.Greedy。同样根据这个习俗，Mr.Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小，并且仍要保证任何人可以从城镇 前往城镇 （因此，这些选出的道路来自将费用作为相应边边权的 「最小生成树」）。如果有多个这样的道路集合，Mr.Greedy 可以选其中的任何一个，只要满足费用和是最小的。
Mr.Greedy 很明确地知道，他从 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 个人经过道路 ，道路 产生的收入为 的积。注意 Mr.Greedy 只能从新道路收取费用，因为原来的道路都不属于他。
Mr.Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路（将在嘉年华的前一天公布），使得他在 条新道路的收入最大。注意 Mr.Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。
你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序 来确定 Mr.Greedy 可以通过他的阴谋获取多少收入。
