题目背景

ICPC2020 WF B

题目描述

By 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.

The 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.

The 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.

It 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.

Figure B.1 illustrates the situation given in both Sample Input 1 and Sample Input 2.

输入格式

The first line of input contains two integers $n$ and $c$, where $n$ ($1 \le n \le 20\,000$) is the number of intersections and $c$ ($1 \le c \le 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 \le u, v \le n; u \ne v$) are the intersections at the ends of a road, and $s$ ($1 \le s \le 10^5$) is the current speed limit of that road in kilometers per hour.

输出格式

Output the minimum cost to upgrade roads and install speed-limit signs such that the town plan satisfies all the rules above.

题目大意

到 3031 年，ICPC 已经变得如此受欢迎，以至于必须建造一个全新的 ICPC 镇来容纳所有参加 World Finals 的队伍。这座城镇设计精美，有完整的道路网。不幸的是，在编制预算时，城市规划者忘记了考虑限速标志的成本。他们要求你帮助他们确定他们需要的最低额外资金。

ICPC 镇的道路网由道路组成，每条道路连接两个十字路口。每条道路都是双向的，并且已经指定了一个速度限制 $s$，对两个方向都有效。为了省钱，ICPC 镇使用了尽可能少的道路。换句话说，从任何交叉口到任何其他交叉口只有一条路线。

限速标志需要安装在所有可能改变任何路线驾驶员限速的地方。更准确地说，如果存在至少两条道路满足不同限速要求的交叉口，那么从该交叉口出发的所有道路都需要在该交叉口安装限速标志。请注意，有些道路可能需要两个限速标志，每端一个。

安装一个限速标志需要花费 $c$ 美元。还可以提高任何道路的安全性和质量，从而提高其限速，从而减少所需限速标志的数量。将一条道路的限速提高 $x$ 公里每小时（双向）需要 $x$ 美元。为了避免投诉，市议会不允许降低任何已经指定的限速。

数据范围：

• $1\leqslant n\leqslant 2\times 10^4$，$1\leqslant c\leqslant 10^5$。
• $1\leqslant s\leqslant 10^5$。

Translated by Eason_AC

5 2
1 2 10
1 3 5
1 4 7
2 5 9

7

5 100
1 2 10
1 3 5
1 4 7
2 5 9

9