Bridges#5372
In a distant country located in the delta of a great river, there were islands, and each island had a city on it. The cities were connected by roads in such a way that between any two cities there existed exactly one route (possibly passing through other cities). However, every road crossed the river by ford, since bridges were not yet known, and traveling along such roads was inconvenient and possible only on horseback.
After the technology for building bridges was discovered, the king decided to replace some of the fords with bridges to make the roads more convenient for travel. Bridges allowed travelers to cross the river even in carriages. The king liked this idea and ordered the construction of as many bridges as possible. However, the country was poor, so only bridges could be built.
The king turned to you, his chief advisor, asking you to develop a construction plan. You must choose fords in such a way that the total travel time between all pairs of cities becomes minimal. Assume that ordinary roads are traversed on horseback, while roads with bridges are traversed by carriage.
The first line contains four integers: n, k~(1 \le k < n \le 10000), s_h and s_c~(1 \le s_h, s_c \le 10^5) — the number of cities, the number of bridges to be built, the speed of a horse, and the speed of a carriage (in meters per second).
Each of the following n - 1 lines contains three integers: b_i, e_i — the cities connected by a road, and l_i~(1 \le l_i \le 10^6) — the length of that road in meters.
Cities are numbered from to , and roads are numbered from to n - 1.
Print integers — the indices of the roads on which bridges must be built. If several optimal solutions exist, you may output any of them.