Bridges

Long ago, a country lay in the delta of a distant river. The country had $n$ islands, with one town on each island. The towns were connected by roads so that there was exactly one route between every pair of towns (possibly passing through some intermediate towns). In other words, the towns and roads form a tree.

Every road crossed the river at a ford. Because bridges were unknown, crossing a ford was uncomfortable and could only be done on horseback.

When bridge-building technology was discovered, the king decided to replace some fords with bridges so that those roads would be easier to travel: a road with a bridge can be crossed by a carriage. The country was poor, so only $k$ bridges could be built.

You must choose the $k$ roads to bridge so that the total travel time over all pairs of towns is as small as possible. A road without a bridge is traveled by horse at speed $s_h$; a road with a bridge is traveled by carriage at speed $s_c$ (speeds are in meters per second). Traversing a single road of length $l$ takes $l / s_h$ by horse or $l / s_c$ by carriage. The travel time between two towns is the sum of the travel times of the roads on the unique route between them, and the total travel time is the sum of that quantity over all unordered pairs of distinct towns.

The first line contains four integers $n$, $k$, $s_h$, and $s_c$: the number of towns, the number of bridges to build ($1 \le k < n \le 10\,000$), the horse speed, and the carriage speed in meters per second ($1 \le s_h, s_c \le 100\,000$).

Each of the next $n - 1$ lines contains three integers $b_i$, $e_i$, and $l_i$: the two towns joined by road $i$ and that road's length in meters ($1 \le l_i \le 10^6$). Towns are numbered from $1$ to $n$, and roads are numbered from $1$ to $n - 1$ in the order they are given.

Output the numbers of the $k$ roads on which to build bridges so that the total travel time is minimized. Print them on one line in increasing order, separated by single spaces.

If several plans achieve the minimum total travel time, output the lexicographically smallest one: among all optimal plans, write each plan's chosen road numbers in increasing order and print the sequence that is lexicographically smallest.

The figure illustrates an example configuration.