408914: GYM103379 J Not a Winter Formal

The winter solstice is fast approaching, and so is the grand ball hosted at the South Pole! You, one of the event planners, have been tasked with selecting a lineup of artists to perform in pairs. The head event planner has given you a list of $$$N-1$$$ pairs of artists who know each other as well as the number of attendees recorded the most recent time a pair duetted together. Coincidentally, every artist that appears at least once on the list knows every other artist on the list either directly or indirectly through a series of acquaintances on the list. The budget allows for up to $$$K$$$ pairs of artists to be invited to the ball, but each performer can only appear in at most one pair and the selected pairs must be a subset of the ones on the list. South Pole management wants to maximize the expected number of people in attendance, which is the sum of the attendees from the previous performances of the each duo. Of course, only a certain programmer can find this expected count to help out with logistical calculations.

The first line of input contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N, K \leq 100000$$$), representing the number of artist pairs that know each other for consideration and the maximum number of pairs that can requested to perform, respectively. Each of the next $$$N-1$$$ lines contains three integers $$$x$$$, $$$y$$$, and $$$p$$$, where $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq N$$$) represent two artists who know each other and $$$p$$$ ($$$1 \leq p \leq 10000$$$) is the number of people that showed up to their last performance.

Output a single integer representing the expected number of people in attendance with an optimal lineup.

8 4
1 2 9
2 3 10
3 4 11
4 5 12
5 6 13
6 7 14
7 8 15

48

8 2
1 2 9
2 3 10
3 4 11
4 5 12
5 6 13
6 7 14
7 8 15

28

4 3
1 2 1
2 3 2
3 4 3

4