ICPC Road Signs

In the year 3031 the ICPC is so popular that a special town has been built for all the World Finals teams. The town has a beautiful road network connecting intersections. Every road is bidirectional and has an assigned speed limit (in km/h). Because the network uses the minimum number of roads (i.e. the network is a tree) there is exactly one route between any two intersections.

Speed‐limit signs must be installed at every intersection where the speed limit changes along some route. More precisely, at an intersection where at least two incident roads have different speed limits, a sign must be installed on every road emanating from that intersection. Note that a road might have two signs (one at each end) if both endpoints are such intersections.

It costs c dollars to install one sign. However, it is possible to improve a road: you may increase its speed limit (in both directions). Increasing a road’s speed limit by Δ km/h costs x·Δ dollars. (Decreasing a speed limit is not allowed.)

Your task is to help the town planners decide the minimum additional funds required so that, after optionally increasing some roads’ speed limits, the necessary signs are installed. Formally, for each road i with original speed limit s_i you may increase it by a nonnegative integer value d_i so that its effective speed is s_i + d_i. At any intersection with at least two incident roads, if the effective speeds of the roads meeting there are not all equal then a speed‐limit sign must be installed on every road emanating from that intersection (and a road may receive a sign on each end).

The total cost is the sum of all speed‐limit sign installation costs and the cost for increasing speeds. That is, if an intersection u (with degree at least 2) has incident roads whose effective speeds are not all equal then a cost of c · deg(u) dollars is incurred (where deg(u) is the degree of u), and if a road’s limit is increased by d km/h, an extra cost of x·d dollars is incurred. Choose the d_i's (one for each road) to minimize the total cost.

A useful observation: if at an intersection the road speeds are equal then no signs are needed there. In other words, to avoid the sign cost at an intersection (with degree ≥ 2) you must equalize the effective speeds on all roads incident to it. However, note that every road appears at two intersections. Hence, if both endpoints of a road decide to equalize, they must agree on its effective speed. In contrast, if a vertex does not equalize, it simply pays a penalty of c · deg(u) dollars (except when deg(u) = 1, in which case no sign is needed). It is not allowed to decrease a speed limit.

Input and output format details follow.

inputFormat

The first line contains three integers: n (the number of intersections), c (the cost per speed‐limit sign), and x (the cost factor for increasing speed limits).

Then follow n − 1 lines. Each of these lines contains three integers u, v, and s describing a road between intersections u and v with an initially assigned speed limit of s km/h. It is guaranteed that the roads form a tree (i.e. there is exactly one simple path between any two intersections). Intersections are numbered from 1 to n.

outputFormat

Output a single integer: the minimum additional funds required (in dollars) so that after the necessary speed‐limit improvements and installations, every driver on every route only experiences changes in speed limits at intersections where the proper signs have been installed.

sample

3 10 1
1 2 5
2 3 7

2