The Cost of Speed Limits
시간 제한14초메모리 제한2048 MB
각 간선에 제한속도가 있는 트리에서, 한 정점에 인접한 간선들의 제한속도가 다르면 그 정점의 모든 간선에 표지판을 설치해야 한다. 간선의 제한속도를 1km/h 올리는 비용이 x일 때, 표지판 설치와 속도 상향을 적절히 선택해 총비용을 최소화한다.
문제
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.
 |  |  |
| (a) Town roads with originally assigned speed limits. | (b) The solution to Sample Input 1 involves installing three signs and upgrading one road. | (c) If c is too high, it is possible to upgrade roads instead, so all of them have the same speed limit. Then we need no signs, as in Sample Input 2. |
Figure B.1: Illustration of the road network and speed limits.
입력
The first line of input contains two integers n and c, where n (1 ≤ n ≤ 20 000) is the number of intersections and c (1 ≤ c ≤ 105) 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 ≤ u, v ≤ n; u ≠ v) are the intersections at the ends of a road, and s (1 ≤ s ≤ 105) 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.