Description

你的程序必须根据给定的输入，给出符合题意的输出：

• 输入包括网络的拓扑结构，升级网络中每台交换机的费用，以及改造网络的费用，还有可以升级的交换机的最大数目 $p$；
• 你必须根据输入，找出一个升级的方案，满足升级后的核心交换机的数目不超过给定的可升级交换机最大值 $p$，且使得总费用最少；
• 其中总费用的计算包括两个部分:
  • 一部分是升级交换机为核心交换机所需要的费用，该部分的费用按照所有的需要升级的交换机所需的费用之和来计算；
  • 另一部分是改造网络所需要的费用，该部分的费用按照所有未升级的交换机到最近的核心交换机的网络路径距离之和来计算；
  • 注意: 当网络中没有任何交换机升级到核心交换机的时候，由于也没有交换机可以连接到核心交换机，所以我们定义此时的总费用为无穷大。

Input Format

第一行为两个正整数 $n(n \leq 400)$ 和 $p$，分别表示网络中交换机的数目（交换机按照 $1$ 到 $n$ 标号）和可升级交换机的最大值。接下来的 $n$ 行每行一个正整数 $c_i$，表示把标号为 $i$ 的交换机升级为核心交换机所需要的费用。

接下来的 $n-1$ 行每行三个正整数 $i$、$j$、$d_{i,j}(d_{i,j}<20000)$，表示编号为 $j$ 的交换机为编号为 $i$ 的交换机的上层交换机，而 $d_{i,j}$ 表示两台交换机之间的网路距离。

Output Format

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

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

Hint

样例说明

评分方法

本题目一共有十个测试点，每个测试点的分数为总分数的 $10\%$。对于每个测试点来说，如果你的答案正确，那么你将得到该测试点全部的分数，否则得 $0$ 分。

注意，本题目的测试数据中有 $8$ 个数据的 $n$ 不超过 $180$。