Bridge Demolition Strategy

During a war, the battlefield consists of \( n \) islands connected by \( n-1 \) bridges, forming a tree (i.e. there is exactly one unique path between any two islands). The enemy headquarters is located on island \(1\). Intelligence indicates that exactly \( k \) of the other islands possess abundant energy resources. Our mission is to destroy some bridges at a minimum total cost such that the enemy at island \(1\) cannot reach any island with energy.

After our operation, the enemy can activate a mysterious machine that not only repairs all the bridges we have demolished but also randomly redistributes the energy resources (with the guarantee that island \(1\) will not be assigned any energy). However, the machine can only be used \( m \) times, so we need to guarantee our plan succeeds in each mission independently.

Objective: In every mission (with \( k \ge 1 \)), we must ensure that no matter how the \( k \) energy-bearing islands (selected from islands \(2, 3, \dots, n\)) are chosen, island \(1\) cannot reach them using the remaining bridges. This is only possible if the connected component containing island \(1\) does not include any other island (i.e. island \(1\) is completely isolated). When \( k = 0 \), no demolition is required.

Input Format: The input begins with three integers \( n \), \( k \), and \( m \). Following that are \( n-1 \) lines, each containing three integers \( u \), \( v \), and \( cost \), representing a bridge connecting islands \( u \) and \( v \) with a demolition cost of \( cost \).

Output Format: Output a single integer representing the minimum total cost required to ensure island \(1\) is isolated (if \( k \ge 1 \)) or 0 if \( k = 0 \).

Note: Since the tree structure guarantees a unique path between any two islands, to completely isolate island \(1\) when \( k \ge 1\), one must remove all bridges directly connected to island \(1\). For each bridge, if it is incident to island \(1\), add its cost. When \( k = 0 \), output 0.

inputFormat

The first line contains three integers \( n \) (the number of islands), \( k \) (the number of islands with energy, excluding island \(1\)), and \( m \) (the number of times the enemy can use the mysterious machine). The following \( n-1 \) lines each contain three integers \( u \), \( v \), and \( cost \) indicating there is a bridge between islands \( u \) and \( v \) with a demolition cost of \( cost \).

outputFormat

Output a single integer: the minimal total demolition cost required so that island \(1\) is isolated from all other islands if \( k \ge 1\). If \( k = 0 \), output 0.

sample

3 1 5
1 2 3
2 3 4

3