P4662 [BalticOI 2008] 黑手党

Byteland 国警方收到了一条匿名举报，其中说当地黑帮老大正计划一次从港口到郊区仓库的运输。警方知道运输的时间并且知道运输需要用到国家的高速公路网。 高速公路网包含双向的高速公路段，每个路段直接连着两个不同的收费站。一个收费站可能与很多其他的收费站相连。汽车只能通过收费站进入或离开高速公路网。据所知，黑帮会距港口边最近的收费站进入高速公路，从距仓库最近的收费站离开（不会在出高速后重新进入）。特警组位于选定的收费站处。当运输车辆进入被监控的收费站时，它就会被警察抓住。 从这个角度看，最简单的办法就是在每个收费站处都安排特警班。然而，控制一个收费站需要特定的费用，每个收费站费用不同。警方想要让花费最小，所以他们需要制定一个收费站的最小控制集，这个集合满足两个条件： - 所有从港口到仓库的交通必须至少经过集合中的一个收费站 - 监控这些收费站的费用（即监控每一个收费站费用之和）最小 你可以假设使用高速公路可以从港口到仓库。 #任务 写一个程序能够： - 从标准输入中读取高速公路网，监控代价和运输的起点和终点 - 找到收费站的最小控制集 - 输出这个集合到标准输出

无

无

**样例解释**  这张图片显示了高速公路网中收费站的编号（在左上角）和控制费用。$1$ 号和 $4$ 号收费站组成了最小控制集，总控制费用为 $5$。 **数据范围** 对于 $40\%$ 的测试数据，$n\le 20$； 对于全部数据，$1\le n\le 200,1\le m \le 2\times 10^4$​​，$1 \le a,b \le n,a≠b$，$1\le c\le 10^7$​​，$1\le x