3616번 - Bridges 스페셜 저지다국어

Once upon a time there was a country in a delta of a far-away river. The country had n islands and there was a town on each island. The towns were connected by roads. There was exactly one route from each town to each other one (possibly passing through some intermediate towns). Unfortunately, each road had to cross the river with a ford, since bridges were not known, so the travel was quite uncomfortable and could only be made by a horse.

When Bridge Building technology was discovered the king decided to build bridges instead of some fords to make roads easier to travel. Bridges would allow fords to be crossed even by carriages. The king liked the idea with bridges and ordered to build as many bridges as possible. Unfortunately, the country was quite poor, so only k bridges could be built.

The king asked you — his major advisor — to develop a bridge building plan. You have to choose k fords in such a way that the sum of travel times between all pairs of towns becomes as small as possible. You must assume that the ordinary roads would be traveled by horses, and roads enhanced with bridges would be traveled by carriages.

The first line of the input file contains four integer numbers: n, k, s_h and s_c — the number of towns in the country, the number of bridges to build (1 ≤ k < n ≤ 10 000), the speed of the horse and the speed of the carriage in meters per second (1 ≤ s_h, s_c ≤ 100 000).

Each of the following n − 1 lines contains three integer numbers: b_i, e_i — the towns connected by the road, and li — the road length in meters (1 ≤ l_i ≤ 10⁶). Towns are numbered from 1 to n, roads are numbered from 1 to n − 1.

Output k numbers — the numbers of roads where the bridges should be built. If there are several possible optimal bridge building plans, output any of them.