Description

Your program must produce output that satisfies the requirements based on the given input:

• The input includes the network topology, the cost to upgrade each switch in the network, the cost to reconstruct links, and the maximum number $p$ of switches that can be upgraded.
• Based on the input, you must find an upgrade plan such that the number of core switches after upgrading does not exceed the given maximum $p$, and the total cost is minimized.
• The total cost consists of two parts:
  • One part is the cost required to upgrade switches to core switches, which is the sum of the upgrade costs of all switches that are upgraded.
  • The other part is the cost required to reconstruct the network, which is the sum of the network path distances from every non-upgraded switch to its nearest core switch.
  • Note: If no switch in the network is upgraded to a core switch, since no switch can be connected to a core switch, we define the total cost in this case to be infinity.

Input Format

The first line contains two positive integers $n(n \leq 400)$ and $p$, representing the number of switches in the network (switches are numbered from $1$ to $n$) and the maximum number of switches that can be upgraded.

The next $n$ lines each contain a positive integer $c_i$, representing the cost to upgrade switch $i$ to a core switch.

The next $n-1$ lines each contain three positive integers $i$, $j$, and $d_{i,j}(d_{i,j}<20000)$, indicating that switch $j$ is an upper-level switch of switch $i$, and $d_{i,j}$ is the network distance between the two switches.

Output Format

The first line of output contains an integer $M$, representing the minimum total cost of your plan.

The next line contains an integer $p_0$, representing the number of switches that need to be upgraded to core switches in your plan.

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

Sample Explanation

Scoring Method

There are ten test points in this problem, and each test point is worth $10\%$ of the total score. For each test point, if your answer is correct, you will get the full score for that test point; otherwise, you will get $0$ points.

Note that in the testdata of this problem, there are $8$ cases where $n$ does not exceed $180$.

Translated by ChatGPT 5