Log Transport

Most of a kingdom is covered by rivers and forests. Small upstream rivers merge into larger rivers, and farther downstream those rivers merge again. In the end, every waterway joins one large river that flows past the kingdom and into the sea.

There are n riverside villages where woodcutters live. Currently, there is only one sawmill, located at the kingdom at the lowest point of the river system. Logs cut in each village must therefore be floated downstream to that sawmill.

To reduce transport cost, k additional sawmills will be built in some of the villages. Once these sawmills exist, logs sent from upstream are processed at the first sawmill they meet while moving downstream. Logs produced in a village that has a sawmill do not need to be transported by river at all.

For every village, you are given the number of logs produced in a year and the distance to the next village, or the kingdom, directly downstream. Since rivers only merge as they flow downstream and never split, there is exactly one path from any village to the kingdom.

Transporting one log for 1 km costs 1. Transporting 2 logs for 5 km costs 2 * 5 = 10. Write a program that chooses where to build the sawmills so that the total transport cost over all villages is minimized.

The first line contains the number of villages excluding the kingdom, n, and the number of new sawmills to build, k. Villages are numbered from 1 to n, and the kingdom is numbered 0.

Each of the next n lines describes one village. The i-th of these lines contains three integers w_i, v_i, and d_i.

• w_i: the number of logs produced in village i
• v_i: the first village, or the kingdom, reached by moving directly downstream from village i
• d_i: the distance from village i to v_i

The constraints are as follows.

• 2 <= n <= 100
• 1 <= k <= 50
• k <= n
• Any possible total transport cost is at most 2,000,000,000.

Print the minimum total cost of transporting all produced logs to the first sawmill they encounter when k new sawmills are built optimally. The existing sawmill at the kingdom may also be the destination.

When an illustration is provided, line segments represent rivers and circles represent villages. The number on a line segment is the distance of that river segment, the number inside a circle is the village number, and the number below a circle is that village's annual log production.

In the illustrated situation, the optimal villages for the two new sawmills are villages 2 and 3. Then the only costs are 1 * 3 for sending the logs from village 4 to village 2, and 1 * 1 for sending the logs from village 1 to the kingdom.