Byteland Lumber Transportation Optimization

In the kingdom of Byteland, almost the entire territory is covered by forests and rivers. Small streams merge into larger rivers until finally all water flows into one huge river that empties into the sea. At the river’s mouth lies the village of Bytetown.

There are $n$ logging villages located along the river, and each village produces a certain amount of timber per year. Bytetown already has a huge sawmill that processes all timber floated down the river. To reduce transportation costs, the king has decided to build $k$ additional sawmills in some of the other villages. When timber is carried downstream, it is processed at the first sawmill encountered. Thus, if a village has its own sawmill then its timber need not be transported farther, saving transportation cost.

All rivers do not bifurcate and form a tree with Bytetown as the root (which already has a sawmill). The cost for transporting timber is computed as follows: for every ton of timber, it costs 1 cent per kilometer.

Assume that if no additional sawmill is built on the path from a village to Bytetown, then the cost incurred for that village is the total distance (summed over all edges on its unique path) multiplied by its timber production. When a sawmill is built at a village, the cost for the entire subtree (i.e. that village and all villages downstream from it) is saved for the edge connecting that village to its parent because the timber is processed locally.

We can model the problem as follows. Let the input consist of an integer $n$ (the number of villages) and an integer $k$ (the count of additional sawmills to build). For the villages, the input format is defined as below:

For village 1 (Bytetown), a single integer $p_1$ is provided, indicating its timber production. For every other village $i$ ($2 \le i \le n$), three integers are given: the index of its parent village, the distance $d_i$ (in kilometers) from village $i$ to its parent, and its timber production $p_i$.

Let $S(v)$ denote the total timber production in the subtree rooted at village $v$. The baseline cost (with no additional sawmills built) is given by [ \text{Baseline Cost} = \sum_{v=2}^{n} S(v) \times d_v. ]

Building a sawmill at a non-root village $v$ saves (S(v) \times d_v) cents. The objective is to choose at most $k$ villages (other than village 1) in which to build sawmills so that the overall transportation cost is minimized.

Your task is to compute the minimum total transportation cost (in cents) after optimally building $k$ additional sawmills.

inputFormat

The input is given as follows:

The first line contains two integers $n$ and $k$, where $n$ is the number of villages and $k$ is the number of additional sawmills to build.

The next line contains a single integer representing the timber production of village 1 (Bytetown).

Then, for villages $2$ to $n$, each line contains three integers: the index of the parent village, the distance $d$ (in kilometers) from this village to its parent, and the timber production of this village.

It is guaranteed that the villages form a tree with village 1 as the root.

outputFormat

Output a single integer: the minimum total transportation cost (in cents) after optimally building the $k$ additional sawmills.

sample

3 1
10
1 5 20
1 3 30

90