Description

The network originally built by the HURRICANE group consists of switches and the network links between them. The switches are connected in a hierarchical structure, with the highest level being the top-level gateway switch, and other switches connected hierarchically to this gateway switch. It is worth noting that any non-gateway switch is directly connected to a switch at a higher level, and any switch can be directly connected to several switches at a lower level.

Recently, due to the limited service capacity of the original network, some switches (including the gateway switch) need to be upgraded to core switches. Due to time constraints, at most $p$ switches (inclusive) can be upgraded to core switches. All remaining switches must be connected directly to one of these core switches by modifying the network.

Both upgrading switches and modifying the network incur certain costs. You are asked to provide a network modification plan such that after the upgrade, every switch is either a core switch or directly connected to a core switch, and the total cost of the modification is minimized.

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

• The input includes the network topology, the cost to upgrade each switch, the cost to modify the network, and the maximum number of switches $p$ that can be upgraded.
• You must find an upgrade plan based on the input that satisfies the condition that the number of core switches after the upgrade does not exceed the given maximum $p$, and the total cost is minimized.
• The total cost consists of two parts:
  • The cost of upgrading switches to core switches, calculated as the sum of the costs of all switches that need to be upgraded.
  • The cost of modifying the network, calculated as the sum of the network path distances from all non-upgraded switches to their nearest core switch.
• Note: If no switches in the network are upgraded to core switches, since no switches can be connected to a core switch, we define the total cost in this case as infinity.

Input

The first line contains two positive integers $n$ ($n \le 400$) and $p$, representing the number of switches in the network (switches are labeled from $1$ to $n$) and the maximum number of switches that can be upgraded, respectively. The next $n$ lines each contain a positive integer $c_i$, representing the cost to upgrade the switch labeled $i$ to a core switch.

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

Output

The first line of your output should be an integer $M$, representing the minimum total cost of your plan. The next line should include an integer $p_0$, representing the number of switches upgraded to core switches in your plan.

Examples

Input 1

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

Output 1

30 
2