9266 - 航道改造

在太空星球上，空间站之间的连接类似于地球上，道路交通网络中的道路。每个空间站都有多条太空航道与其他空间站相连，这些太空航道可以双向通行。与地球上的道路一样，每条太空航道都有一个负载能力，表示该航道的繁忙程度。负载能力越小，表示该航道越拥挤，需要进行改造。
球长希望优化太空航道的连通性和效率，同时尽量节约资源。为了实现这一目标，我们需要解决以下几个关键问题：
连通性要求：确保所有空间站之间都能通过一系列太空航道直接或间接相连。这意味着任意两个空间站之间都存在一条通路，使得宇航员能够从一个空间站到达另一个空间站。
最小改造量：在满足连通性要求的情况下，需要尽量减少改造的太空航道数量。这意味着我们要选择最少数量的太空航道进行改造，以节约资源和时间，并最大程度地减少对太空环境的干扰。
优先改造拥挤航道：在满足前两个要求的前提下，我们应优先改造那些拥挤的太空航道，即负载能力较小的航道。通过改造拥挤航道，我们可以提高太空交通的流畅性和安全性，减少交通事故的发生率，并提升宇航员的航行体验。
为了实现这些目标，我们可以采用一系列太空工程技术，例如利用太空船搭载自动化机器人进行改造、利用空间站的能源和资源支持改造工程、设计智能航行路径规划算法等。通过综合利用技术手段，我们可以高效地实现球长提出的要求，优化太空航道的结构和性能，提升太空交通的效率和安全性。

第一行有两个整数 n，m。表示城市有n 个空间站，m条太空航道。
接下来m行是对每条太空航道的描述，每行三个整数u，v，c表示空间站u和v之间有太空航道相连，负载能力为c。

两个整数 s，max。表示你选出了几条太空航道，负载能力最大的那条道路的负载能力是多少。

【样例1解释】

上图为样例构造出来的星球太空航道图，红色路线为选中修改的路线，共3条，3条中负载能力最大为6。
【数据范围】 对于全部数据，满足1≤n≤300，1≤c≤10^4，1≤m≤8000。

云南编程挑战赛