P6961 [NEERC 2017] Journey from Petersburg to Moscow

To conduct The World Programming Cup $2112$ a network of wonderful toll roads was build in European part of Russia. This network consists of $m$ bidirectional roads that connect $n$ cities. Each road connects exactly two distinct cities, no two roads connect the same pair of cities, and it is possible to travel from any city to any other city using only this road network. Moreover, to ease the process of charging, no two roads intersect outside of the cities. Each road is assigned some individual positive cost. Normally, if a driver makes a trip using some of these toll roads, at the end of his journey he would be charged the total cost equal to the sum of individual costs of all roads he has used. To increase the popularity of car travels between two capitals, the operator company Radishchev Inc introduced a special offer: make a journey from Saint Petersburg to Moscow and pay for only $k$ most expensive roads along your path. Formally, let some path consists of $l$ roads. Denote as $c_{1}$ the cost of the most expensive road along this path, as $c_{2}$ the second most expensive and so on. Thus, we have a sequence $c_{1} \ge c_{2} \ge c_{3} \ge $ . . . $ \ge c_{l}$ of individual costs of all roads along the chosen path. If $l \le k$ , then the path is too short and the driver pays the sum of all individual costs as usual, i.e . $Σ^{l}_{i=1}c_{i}.$ If $l > k$ , then the driver only pays for $k$ most expensive roads, that is $Σ^{k}_{i=1}c_{i}.$ As the chief analyst of Radishchev Inc you were assigned a task to compute the cheapest possible journey from Saint Petersburg to Moscow.

无

无

Time limit: 3 s, Memory limit: 512 MB.