Description

从前，HURRICANE小组承担了一项重要的工作——把校园内的计算机接入到Internet上面去。他们首先把每个人的

计算机编组并把同一组的连在一台基层础交换机上，然后设立了一个对外的顶级网关交换机，再用其他的一些中间

交换机把这些交换机一层一层的连接起来接到顶级网关交换机上。而且交换机都是严格的按照一层一层的连接起来

的，低一层的交换机只会连接到一台高一层的交换机上面，但一台高层的交换机可能同时和几台低一层的交换机相

连。但最近，由于原来架设的网络服务有限，需要把网络中的一些交换机升级为核心交换机并对整个网络提供更多

的服务。不过由于改造的时间所限，只来得及把不超过p台交换机升级为核心交换机，而所有剩下的交换机则需要

通过改造网络的方法和这几台核心交换机直接连接。但是无论是升级交换机还是改造网络都需要花费一定的资金。

现在请你给出一个改造网络的方案。使得按照该方案升级后每一个交换机要么是核心交换机，要么直接和核心交换

机相连。并且要求提供的方案使改造所用的总费用最小。

【任务描述】你的程序必须根据给出的输入，提供符合题意的输出：? 输入包括网络的拓扑结构，升级网络中每台

交换机的费用，以及改造网络的费用，还有可以升级的交换机的最大数目；? 你必须根据输入，找出一个升级的方

案，满足升级后的核心交换机的数目不超过给定的可升级交换机最大值p，且使得总费用最少；? 其中总费用的计

算包括两个部分：? 一部分是升级交换机为核心交换机所需要的费用，该部分的费用按照所有的需要升级的交换机

所需的费用之和来计算；? 另一部分是改造网络所需要的费用，该部分的费用按照所有未升级的交换机到最近的核

心交换机的距离之和来计算；? 如果两台交换机直接相连，那么该距离即为他们之间的网络距离；? 如果两台交换

机是通过其他的交换机间接连接在一起的，那么它们之间的距离定义为它们之间的唯一一条路径上相邻的交换机之

间网络长度之和；? 注意：当网络中没有任何交换机升级到核心交换机的时候，由于也没有交换机可以连接到核心

交换机，所以我们定义此时的总费用为无穷大。

Input

第一行为两个整数n（n ≤ 400）和p，分别表示网络中交换机的数目和可升级交换机的最大值。

接下来的n行每行一个正整数ci，表示把标号为i的交换机升级为核心交换机所需要的费用。

接下来的n-1行每行三个整数i、j、di,j，表示编号为i的交换机为编号为j的交换机的上层交换机，

而di,j表示两台交换机之间的网络长度。

你的输出第一行为一个整数M，表示你的方案的最小总费用。

接下来一行包括一个整数p0，表示你的方案所需要升级为核心交换机的交换机数目。

23
1