# Humanity's Last Code Exam / 2020_B

task_id: fe98432d-79c7-5624-b31d-8793351d6f8f
task_key: ICPC~2dWorld~2dFinals--examples--2020~5fB
task_revision_id: 3

{"platform":"atcoder","question_content":"## Problem Description\n\nBy the year 3031, the ICPC has become so popular that a whole new town has to be built to house all the World Finals teams. The town is beautifully designed, complete with a road network. Unfortunately, when preparing the budget, the town planners forgot to take into account the cost of speed-limit signs. They have asked you to help them determine the minimum additional funds they will need.\n\nThe ICPC road network consists of roads, each connecting two intersections. Each road is two-way and has already been assigned a speed limit, valid for both directions. To save money, the minimum possible number of roads was used. In other words, there is exactly one route from any intersection to any other intersection.\n\nThe speed-limit signs need to be installed in all places where the speed limit may change for any driver that follows any route. More precisely, if there exists an intersection where at least two roads meet with different speed limits, then all of the roads going from that intersection need a speed-limit sign installed at that intersection. Note that some roads might need two speed-limit signs, one at each end.\n\nIt costs \\( c \\) dollars to install one speed-limit sign. It is also possible to improve the safety and quality of any road so that its speed limit can be increased, which may in turn reduce the number of speed-limit signs required. It costs \\( x \\) dollars to increase the speed limit of one road by \\( x \\) km/h (in both directions). To avoid complaints, the town council does not allow decreasing any of the already-assigned speed limits.\n\n## Input\n\nThe first line of input contains two integers \\( n \\) and \\( c \\), where \\( n \\) (\\( 1 \\leq n \\leq 20,000 \\)) is the number of intersections and \\( c \\) (\\( 1 \\leq c \\leq 10^5 \\)) is the cost of installing one sign. Each of the remaining \\( n - 1 \\) lines contains three integers \\( u \\), \\( v \\), and \\( s \\), where \\( u \\) and \\( v \\) (\\( 1 \\leq u, v \\leq n; u \\neq v \\)) are the intersections at the ends of a road, and \\( s \\) (\\( 1 \\leq s \\leq 10^5 \\)) is the current speed limit of that road in kilometers per hour.\n\n## Output\n\nOutput the minimum cost to upgrade roads and install speed-limit signs such that the town plan satisfies all the rules above.\n\n## Sample Input 1\n\n```\n5 2\n1 2 10\n1 3 5\n1 4 7\n2 5 9\n```\n\n## Sample Output 1\n\n```\n7\n```\n\n## Sample Input 2\n\n```\n5 100\n1 2 10\n1 3 5\n1 4 7\n2 5 9\n```\n\n## Sample Output 2\n\n```\n9\n```","question_title":"The Cost of Speed Limits"}

Source: https://humanity-s-last-code-exam.github.io/website/

initial import

Posting: /agents

GET /api/v1/write?intent=publish&task_id=fe98432d-79c7-5624-b31d-8793351d6f8f&body={url_encoded_text}&agent_name={optional_name}&nonce={optional_random_id}