1261: 网络改造

　　HURRICANE 小组原来构建的网络由网络上的交换机及其间的网路构成。交换机分级连接，最高级的为顶级的网关交换机，其他交换机分级相连到该网关交换机上。但值得注意的是，任一台非网关交换机与一台高一级的交换机直接相连。而任一台交换机均可以与几台低一级的交换机直接相连。 　　但最近，由于原来架设的网络服务有限，需要把网络中的一些交换机（包括网关交换机）升级为核心交换机。由于改造的时间所限，只来得及把不超过 p 台（含 p 台）交换机升级为核心交换机，而所有剩下的交换机则需要通过改造网路的方法和这几台核心交换机直接连接。 　　但是无论是升级交换机还是改造网络都需要花费一定的资金。现在请你给出一个改造网络的方案。使得按照该方案升级后每一个交换机要么是核心交换机，要么直接和核心交换机相连。并且要求提供的方案使改造所用的总费用最小。 　　你的程序必须根据给定的输入，给出符合题意的输出： 　　●输入包括网络的拓扑结构，升级网络中每台交换机的费用，以及改造网络的费用，还有可以升级的交换机的最大数目 p； 　　●你必须根据输入，找出一个升级的方案，满足升级后的核心交换机的数目不超过给定的可升级交换机最大值 p，且使得总费用最少； 　　●其中总费用的计算包括两个部分： 　　　■一部分是升级交换机为核心交换机所需要的费用，该部分的费用按照所有的需要升级的交换机所需的费用之和来计算； 　　　■另一部分是改造网络所需要的费用，该部分的费用按照所有未升级的交换机到最近的核心交换机的网络路径距离之和来计算； 　　　■注意：当网络中没有任何交换机升级到核心交换机的时候，由于也没有交换机可以连接到核心交换机，所以我们定义此时的总费用为无穷大。

　　第一行为两个正整数n（n ≤ 400）和 p，分别表示网络中交换机的数目（交换机按照 1 到 n 标号）和可升级交换机的最大值。接下来的 n 行每行一个正整数c_i，表示把标号为 i 的交换机升级为核心交换机所需要的费用。 　　接下来的 n-1 行每行三个正整数 i、j、d_i,j（d_i,j < 20000），表示编号为j的交换机为编号为 i 的交换机的上层交换机，而 d_i,j 表示两台交换机之间的网路距离。

　　你的输出第一行为一个整数 M，表示你的方案的最小总费用。接下来一行包括一个整数 p₀，表示你的方案所需要升级为核心交换机的交换机数目。

7 2
7
1
7
7
7
1
2
2 1 2
3 2 4
6 5 2
7 5 9
5 1 3
4 1 7

30
2